1104281048f1e2a2290dbbc1c9.pdf

while(dW 1e-15),%Choose a sample randomly i =randperm(L);phi=train_features(:,i(1);net_k=W*phi;y_star=find(net_k=max(net_k);y_star=y_star(1);%Just in case two have the same weights!oldW=W;W =W+eta*phi*gamma(win_width*abs(net_k-y_star);W =W./(ones(D,1)*sqrt(sum(W.2);eta=eta*deta;dW =sum(sum(abs(oldW-W);iter=iter+1;if(plot_on=1),%Assign each of the features to a center dist =W*train_features;m,label =max(dist);centers =zeros(D,Nmu);for i=1:Nmu,in=find(label=i);if isempty(in)centers(:,i)=mean(train_features(:,find(label=i);else centers(:,i)=nan;end end plot_process(centers)end if(iter/100=floor(iter/100),disp(Iteration number num2str(iter)end end%Assign a weight to each featurelabel=zeros(1,L);for i=1:L,net_k =W*train_features(:,i);label(i)=find(net_k=max(net_k);end%Find the target for each weight and the new featurestargets =zeros(1,Nmu);features=zeros(D,Nmu);for i=1:Nmu,in =find(label=i);if isempty(in),targets(i)=sum(train_targets(in)/length(in).5;if length(in)=1,features(:,i)=train_features(:,in);else features(:,i)=mean(train_features(:,in);end endendDavid G.StorkElad Yom-TovComputer Manualin MATLABto accompanyPatternClassification Appendix to the Computer Manual in MATLAB to accompany Pattern Classification(2nd ed.)David G.Stork and Elad Yom-TovBy using the Classification toolbox you agree to the following licensing terms:NO WARRANTYTHERE IS NO WARRANTY FOR THE PROGRAMS,TO THE EXTENT PERMITTED BY APPLICABLE LAW.EXCEPT WHEN OTHERWISE STATED IN THE WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES PROVIDE THE PROGRAMS“AS IS”WITHOUT WARRANTY OF ANY KIND,EITHER EXPRESSED OR IMPLIED,INCLUDING,BUT NOT LIMITED TO,THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAMS ARE WITH YOU.SHOULD THE PROGRAMS PROVE DEFECTIVE,YOU ASSUME THECOST OF ALL NECESSARY SERVICING,REPAIR OR CORRECTION.IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING WILL ANY COPYRIGHT HOLDER,OR ANY OTHER PARTY WHO MAY MODIFY AND/OR REDISTRIBUTE THE PROGRAMS,BE LIABLE TO YOU FOR DAMAGES,INCLUDING ANY GENERAL,SPECIAL,INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THEUSE OR INABILITY TO USE THE PROGRAM(INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER PROGRAMS),EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.5Preface 7APPENDIXProgram descriptions 9Chapter 210Chapter 319Chapter 433Chapter 540Chapter 667Chapter 784Chapter 893Chapter 9104Chapter 10112References 145Index 147Contents6 7This Appendix is a pre-publication version to be included in the furthcoming ver-sion of the Computer Manual to accompany Pattern Classification,2nd Edi-tion.It includes short descriptions of the programs in the classification toolbox invoked directly by users.Additional information and updates are available from th e authors web site at http:/www.yom-tov.infoWe wish you the best of luck in your studies and research!David G.StorkElad Yom-TovPreface 8 9APPENDIXProgram descriptionsBelow are short descriptions of the programs in the classification toolbox invoked directly by users.This listings are organized by chapter in Pattern Classification,and in some cases include pseudo-code.Not all programs here appear in the textbook and not every minor variant on an algorithm in the textbook appears here.While most classification programs take input data sets and targets,some classification and feature selection programs have associated additional inputs and outputs,as listed.You can obtain further specific information on the algo-rithms by consulting Pattern Classification and information on the MATLAB code by using its help com-mand.10 Program descriptionsPrograms for Chapter 2Chapter 2Marginalization Function name:MarginalizationDescription:Compute the marginal distribution of a multi-dimensional histogram or distribution as well as the marginal prob-abilities for test patterns given the“good”features.Syntax:predicted_targets=marginalization(training_patterns,training_targets,test_patterns,parameter vector);Parameters:1.The index of the missing feature.2.The number of patterns with which to compute the marginal.Program descriptions 11 Programs for Chapter 2Minimum cost classifierFunction name:minimum_costDescription:Perform minimum-cost classification for known distributions and cost matrix ij.Syntax:predicted_targets=minimum_cost(training_patterns,training_targets,test_patterns,parameter vector);Parameter:The cost matrix ij.12 Program descriptionsPrograms for Chapter 2Normal Density Discriminant FunctionFunction name:NNDFDescription:Construct the Bayes classifier by computing the mean and d-by-d covariance matrix of each class and then use them to construct the Bayes decision region.Syntax:predicted_targets=NNDF(training_patterns,training_targets,test_patterns,parameter vector);Parameters:The discriminant function(probability)for any test pattern.Program descriptions 13 Programs for Chapter 2StumpsFunction name:StumpsDescription:Determine the threshold value on a single feature that will yield the lowest training error.This classifier can be thought of as a linear classifier with a single weight that differs from zero.Syntax:predicted_targets=Stumps(training_patterns,training_targets,test_patterns,parameter vector);predicted_targets,weights=Stumps(training_patterns,training_targets,test_patterns,parameter vector);Parameter:Optional:A weight vector for the training patterns.Additional outputs:The weight vector for the linear classifier arising from the optimal threshold value.14 Program descriptionsPrograms for Chapter 2Discrete Bayes Classifier Function name:Discrete_BayesDescription:Perform Bayesian classification on feature vectors having discrete values.In this implementation,discrete fea-tures are those that have no more than one decimal place.The program bins the data and then computes the prob-ability of each class.The program then computes the classification decision based on standard Bayes theory.Syntax:predicted_targets=Discrete_Bayes(training_patterns,training_targets,test_patterns,parameter vector);Parameters:NoneProgram descriptions 15 Programs for Chapter 2Multiple Discriminant AnalysisFunction name:MultipleDiscriminantAnalysisDescription:Find the discriminants for a multi-category problem.The discriminant maximizes the ratio of the between-class variance to that of the in-class variance.Syntax:new_patterns,new_targets=MultipleDiscriminantAnalysis(training_patterns,training_targets);new_patterns,new_targets,feature_weights=MultipleDiscriminantAnalysis(training_patterns,training_targets);Additional outputs:The weight vectors for the discriminant boundaries.16 Program descriptionsPrograms for Chapter 2BhattacharyyaFunction name:BhattacharyyaDescription:Estimate the Bhattacharyya error rate for a two-category problem,assuing Gaussianity.The bound is given by:Syntax:error_bound=Bhattacharyya(mu1,sigma1,mu2,sigma2,p1);Input variables:1.mu1,mu2 -The means of class 1 and 2,respectively.2.sigma1,sigma2 -The covariance of class 1 and 2,respectively.3.p1 -The probability of class 1.k12-18-12()t12()112()12-12212-ln+=Program descriptions 17 Programs for Chapter 2ChernoffFunction name:ChernoffDescription:Estimate the Chernoff error rate for a two-category problem.The error rate is computed through the following equation:Syntax:error_bound=Chernoff(mu1,sigma1,mu2,sigma2,p1);Input variables:1.mu1,mu2 -The means of class 1 and 2,respectively.2.sigma1,sigma2 -The covariance of class 1 and 2,respectively.3.p1 -The probability of class 1.mine1()2-21()T11()2+121()12-11()2+121-ln+18 Program descriptionsPrograms for Chapter 2Discriminability Funciton name:DiscriminabilityDescription:Compute the discriminability d in the Receiver Operating Characteristic(ROC)curve.Syntax:d_tag=Discriminability(mu1,sigma1,mu2,sigma2,p1);Input variables:1.mu1,mu2 -The means of class 1 and 2,respectively.2.sigma1,sigma2 -The covariance of class 1 and 2,respectively.3.p1 -The probability of class 1.Program descriptions 19 Programs for Chapter 3Chapter 3Maximum-Likelihood ClassifierFunction name:MLDescription:Compute the maximum-likelihood estimate of the mean and covariance matrix of each class and then uses the results to construct the Bayes decision region.This classifier works well if the classes are uni-modal,even when they are not linearly seperable.Syntax:predicted_targets=ML(training_patterns,training_targets,test_patterns,);20 Program descriptionsPrograms for Chapter 3Maximum-Likelihood Classifier assuming Diagonal Covariance MatricesFunction name:ML_diagDescription:Compute the maximum-likelihood estimate of the mean and covariance matrix(assumed diagonal)of each class and then uses the results to construct the Bayes decision region.This classifier works well if the classes are uni-modal,even when they are not linearly seperable.Syntax:predicted_targets=ML_diag(training_patterns,training_targets,test_patterns,);Program descriptions 21 Programs for Chapter 3GibbsFunction name:GibbsDescription:This program finds the probability that the training data comes from a Gaussian distribution with known param-eters,i.e.,P(D|).Then,using P(D|),the program samples the parameters according to the Gibbs method,and finally uses the parameters to classify the test patterns.Syntax:predicted_targets=Discrete_Bayes(training_patterns,training_targets,test_patterns,input parameter);Parameter:Resolution of the input features(i.e.,the number of bins).22 Program descriptionsPrograms for Chapter 3Fishers Linear DiscriminantFunction name:FishersLinearDiscriminantDescription:Computes the Fisher linear discriminant for a pair of distributions.The Fisher linear discriminant attempts to maximize the ratio of the between-class variance to that of the in-class variance.This is done by reshaping the data through a linear weight vector computed by the equasion:where SW is the in-class(or within-class)scatter matrix.Syntax:new_patterns,new_targets=FishersLinearDiscriminant(training_patterns,training_targets,);new_patterns,new_targets,weights=FishersLinearDiscriminant(training_patterns,training_targets,);Additional outputs:The weight vector for the linear classifier.wSW1m1m2()=Program descriptions 23 Programs for Chapter 3Local Polynomial ClassifierFunction name:Local_PolynomialDescription:This nonlinear classification algorithm works by building a classifier based on a local subset of training points,and classifies the test points according to those local classifiers.The method randomly selects a predetermined number of the training points and then assign each of the test points to the nearest of the points so selected.Next,the method builds a logistic classifier around these selected points,and finally classifies the points assigned to it.Syntax:predicted_targets=Local_Polynomial(training_patterns,training_targets,test_patterns,input parameter);Input parameter:Number of(local)points to select for creation of a local polynomial or logistic classifier.24 Program descriptionsPrograms for Chapter 3Expectation-MaximizationFunction name:Expectation_MaximizationDescription:Estimate the means and covariances of component Gaussians by the method of expectation-maximization.Pseudo-code:begin initialize 0,T,do E step:compute M step:until return endSyntax:predicted_targets=EM(training_patterns,training_targets,test_patterns,input parameters);predicted_targets,estimated_parameters=EM(training_patterns,training_targets,test_patterns,input parameters);i0ii1+Q ;i()i1+maxQ ;i()argQ i1+;i()Q i;i1()Ti1+Program descriptions 25 Programs for Chapter 3Input parameters:The number of Gaussians for each class.Additional outputs:The estimated means and covariances of Gaussians.Example:These figures show the results of running the EM algorithm with different parameter values.The left figure shows the decision region obtained when the wrong number of Gaussians is entered,while the right shows the decision region when the correct number of Gaussians in each class is entered.26 Program descriptionsPrograms for Chapter 3Multivariate Spline ClassificationFunction name:Multivariate_SplinesDescription:This algorithm fits a spline to the histogram of each of the features of the data.The algorithm then selects the spline that reduces the training error the most,and computes the associated residual of the prediction error.The process iterates on the remaining features,until all have been used.Then,the prediction of each spline is evalu-ated independently,and the weight of each spline is computed via the pseudo-inverse.This algorithm is typically used for regression but here is used for classification.Syntax:predicted_targets=Multivariate_Splines(training_patterns,training_targets,test_patterns,input parameters);Input parameters:1.The degree of the splines.2.The number of knots per spline.Program descriptions 27 Programs for Chapter 3Whitening transformFunction name:Whitening_transformDescription:Apply the whitening transform to a d-dimensional data set.The algorithm first subtracts the sample mean from each point,and then multiplies the data set by the inverse of the square root of the covariance matrix.Syntax:new_patterns,new_targets=Whitening_transform(training_patterns,training_targets,);new_patterns,new_targets,means,whiten_mat=Whitening_transform(training_patterns,training_targets,);Additional outputs:1.The whitening matrix.2.The means vector.28 Program descriptionsPrograms for Chapter 3Scaling transformFunction name:Scaling_transformDescription:Standardize the data,that is,transforms a data set so that it has zero mean and unit variance along each coordi-nate.This scaling is recommended as preprocessing for data presented to a neural network classifier.Syntax:new_patterns,new_targets=Scaling_transform(training_patterns,training_targets,);new_patterns,new_targets,means,variance_mat=Scaling_transform(training_patterns,training_targets,);Additional outputs:1.The variance matrix.2.The means vector.Program descriptions 29 Programs for Chapter 3Hidden Markov Model Forward AlgorithmFunction name:HMM_ForwardDescription:Compute the probability that a test sequence VT was generated by a given hidden Markov model according to the Forward algorithm.Note:This algorithm is in the“Other”subdirectory.Pseudo-code:begin initialize,aij,bjk,visible sequence VT,j(0)for until t=Treturn for the final stateendSyntax:Probability_matrix,Probability_matrix_through_estimation_stages=HMM_Forward(Transition_prob_matrix,Output_generation_mat,Initial_state,Observed output sequence);t0tt1+it()jt1+()aijbjkv t1+()j1=cP VT()0T()30 Program descriptionsPrograms for Chapter 3Hidden Markov Model Backward AlgorithmFunction name:HMM_BackwardDescription:Compute the probability that a test sequence VT was generated by a given hidden Markov model according to the Backward algorithm.Learning in hidden Markov models via the Forward-Backward algo