/* Ċ Ġ* ĠCopyright Ġ( c ) Ġ 2 0 1 0 - 2 0 2 1 ĠHa if eng ĠLi . ĠAll Ġrights Ġreserved . Ċ Ġ* Ċ Ġ* ĠSm ile Ġis Ġfree Ġsoftware : Ġyou Ġcan Ġredistribute Ġit Ġand / or Ġmodify Ċ Ġ* Ġit Ġunder Ġthe Ġterms Ġof Ġthe ĠGNU ĠGeneral ĠPublic ĠLicense Ġas Ġpublished Ġby Ċ Ġ* Ġthe ĠFree ĠSoftware ĠFoundation , Ġeither Ġversion Ġ 3 Ġof Ġthe ĠLicense , Ġor Ċ Ġ* Ġ( at Ġyour Ġoption ) Ġany Ġlater Ġversion . Ċ Ġ* Ċ Ġ* ĠSm ile Ġis Ġdistributed Ġin Ġthe Ġhope Ġthat Ġit Ġwill Ġbe Ġuseful , Ċ Ġ* Ġbut ĠWITHOUT ĠANY ĠWARRANTY ; Ġwithout Ġeven Ġthe Ġimplied Ġwarranty Ġof Ċ Ġ* ĠMERCHANTABILITY Ġor ĠFITNESS ĠFOR ĠA ĠPARTICULAR ĠPURPOSE . Ġ ĠSee Ġthe Ċ Ġ* ĠGNU ĠGeneral ĠPublic ĠLicense Ġfor Ġmore Ġdetails . Ċ Ġ* Ċ Ġ* ĠYou Ġshould Ġhave Ġreceived Ġa Ġcopy Ġof Ġthe ĠGNU ĠGeneral ĠPublic ĠLicense Ċ Ġ* Ġalong Ġwith ĠSm ile . Ġ ĠIf Ġnot , Ġsee Ġ< https :// www . gnu . org / licenses />. Ċ Ġ*/ Ċ Ċ package Ġsm ile . classification Ċ Ċ import Ġjava . util . Optional Ċ import Ġjava . util . stream . Long Stream Ċ import Ġsm ile . base . cart . Split Rule Ċ import Ġsm ile . base . ml p . Layer Builder Ċ import Ġsm ile . base . r bf . R BF Ċ import Ġsm ile . data . DataFrame Ċ import Ġsm ile . data . formula . Formula Ċ import Ġsm ile . math . Math Ex Ċ import Ġsm ile . math . Time Function Ċ import Ġsm ile . math . distance . Distance Ċ import Ġsm ile . math . kernel . M erc er Kernel Ċ import Ġsm ile . neighbor . K NN Search Ċ import Ġsm ile . stat . distribution . Distribution Ċ Ċ /** Ċ Ġ* ĠK - nearest Ġneighbor Ġclassifier . Ċ Ġ* ĠThe Ġk - nearest Ġneighbor Ġalgorithm Ġ( k - NN ) Ġis Ċ Ġ* Ġa Ġmethod Ġfor Ġclass ifying Ġobjects Ġby Ġa Ġmajority Ġvote Ġof Ġits Ġneighbors , Ċ Ġ* Ġwith Ġthe Ġobject Ġbeing Ġassigned Ġto Ġthe Ġclass Ġmost Ġcommon Ġamong st Ġits Ġk Ċ Ġ* Ġnearest Ġneighbors Ġ( k Ġis Ġa Ġpositive Ġinteger , Ġtypically Ġsmall ). Ċ Ġ* Ġk - NN Ġis Ġa Ġtype Ġof Ġinstance - based Ġlearning , Ġor Ġlazy Ġlearning Ġwhere Ġthe Ċ Ġ* Ġfunction Ġis Ġonly Ġapprox imated Ġlocally Ġand Ġall Ġcomputation Ċ Ġ* Ġis Ġdeferred Ġuntil Ġclassification . Ċ Ġ* Ċ Ġ* ĠThe Ġbest Ġchoice Ġof Ġk Ġdepends Ġupon Ġthe Ġdata ; Ġgenerally , Ġlarger Ġvalues Ġof Ċ Ġ* Ġk Ġreduce Ġthe Ġeffect Ġof Ġnoise Ġon Ġthe Ġclassification , Ġbut Ġmake Ġboundaries Ċ Ġ* Ġbetween Ġclasses Ġless Ġdistinct . ĠA Ġgood Ġk Ġcan Ġbe Ġselected Ġby Ġvarious Ċ Ġ* Ġhe uristic Ġtechniques , Ġe . g . Ġcross - validation . ĠIn Ġbinary Ġproblems , Ġit Ġis Ċ Ġ* Ġhelpful Ġto Ġchoose Ġk Ġto Ġbe Ġan Ġodd Ġnumber Ġas Ġthis Ġavoids Ġtied Ġvotes . Ċ Ġ* Ċ Ġ* ĠA Ġdraw back Ġto Ġthe Ġbasic Ġmajority Ġvoting Ġclassification Ġis Ġthat Ġthe Ġclasses Ċ Ġ* Ġwith Ġthe Ġmore Ġfrequent Ġinstances Ġtend Ġto Ġdom inate Ġthe Ġprediction Ġof Ġthe Ċ Ġ* Ġnew Ġobject , Ġas Ġthey Ġtend Ġto Ġcome Ġup Ġin Ġthe Ġk Ġnearest Ġneighbors Ġwhen Ċ Ġ* Ġthe Ġneighbors Ġare Ġcomputed Ġdue Ġto Ġtheir Ġlarge Ġnumber . ĠOne Ġway Ġto Ġover come Ċ Ġ* Ġthis Ġproblem Ġis Ġto Ġweight Ġthe Ġclassification Ġtaking Ġinto Ġaccount Ġthe Ċ Ġ* Ġdistance Ġfrom Ġthe Ġtest Ġpoint Ġto Ġeach Ġof Ġits Ġk Ġnearest Ġneighbors . Ċ Ġ* Ċ Ġ* ĠO ft en , Ġthe Ġclassification Ġaccuracy Ġof Ġk - NN Ġcan Ġbe Ġimproved Ġsignificantly Ċ Ġ* Ġif Ġthe Ġdistance Ġmetric Ġis Ġlearned Ġwith Ġspecialized Ġalgorithms Ġsuch Ġas Ċ Ġ* ĠLarge ĠMargin ĠNe arest ĠNe ighbor Ġor ĠNe ighbor hood ĠComponents ĠAnalysis . Ċ Ġ* Ċ Ġ* ĠNe arest Ġneighbor Ġrules Ġin Ġeffect Ġcompute Ġthe Ġdecision Ġboundary Ġin Ġan Ċ Ġ* Ġimplicit Ġmanner . ĠIt Ġis Ġalso Ġpossible Ġto Ġcompute Ġthe Ġdecision Ġboundary Ċ Ġ* Ġitself Ġexplicitly , Ġand Ġto Ġdo Ġso Ġin Ġan Ġefficient Ġmanner Ġso Ġthat Ġthe Ċ Ġ* Ġcomputational Ġcomplexity Ġis Ġa Ġfunction Ġof Ġthe Ġboundary Ġcomplexity . Ċ Ġ* Ċ Ġ* ĠThe Ġnearest Ġneighbor Ġalgorithm Ġhas Ġsome Ġstrong Ġconsistency Ġresults . ĠAs Ċ Ġ* Ġthe Ġamount Ġof Ġdata Ġapproaches Ġinfinity , Ġthe Ġalgorithm Ġis Ġguaranteed Ġto Ċ Ġ* Ġyield Ġan Ġerror Ġrate Ġno Ġworse Ġthan Ġtwice Ġthe ĠBay es Ġerror Ġrate Ġ( the Ġminimum Ċ Ġ* Ġach ie vable Ġerror Ġrate Ġgiven Ġthe Ġdistribution Ġof Ġthe Ġdata ). Ġk - NN Ġis Ċ Ġ* Ġguaranteed Ġto Ġapproach Ġthe ĠBay es Ġerror Ġrate , Ġfor Ġsome Ġvalue Ġof Ġk Ġ( where Ġk Ċ Ġ* Ġincreases Ġas Ġa Ġfunction Ġof Ġthe Ġnumber Ġof Ġdata Ġpoints ). Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġk - nearest Ġneighbor Ġsearch Ġdata Ġstructure Ġof Ġtraining Ġinstances . Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ġin Ġ[ 0 , Ġc ), Ġwhere Ġc Ġis Ġthe Ġnumber Ġof Ġclasses . Ċ Ġ* Ġ@ param Ġk Ġthe Ġnumber Ġof Ġneighbors Ġfor Ġclassification . Ċ Ġ*/ Ċ fun Ġ< T > Ġk nn ( x : ĠK NN Search < T , ĠT >, Ġy : ĠInt Array , Ġk : ĠInt ): ĠK NN < T > Ġ{ ĊĠĠĠ Ġreturn ĠK NN ( x , Ġy , Ġk ) Ċ } Ċ Ċ /** Ċ Ġ* ĠK - nearest Ġneighbor Ġclassifier . Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġtraining Ġsamples . Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ġin Ġ[ 0 , Ġc ), Ġwhere Ġc Ġis Ġthe Ġnumber Ġof Ġclasses . Ċ Ġ* Ġ@ param Ġdistance Ġthe Ġdistance Ġmeasure Ġfor Ġfinding Ġnearest Ġneighbors . Ċ Ġ* Ġ@ param Ġk Ġthe Ġnumber Ġof Ġneighbors Ġfor Ġclassification . Ċ Ġ*/ Ċ fun Ġ< T > Ġk nn ( x : ĠArray < T >, Ġy : ĠInt Array , Ġk : ĠInt , Ġdistance : ĠDistance < T >): ĠK NN < T > Ġ{ ĊĠĠĠ Ġreturn ĠK NN . fit ( x , Ġy , Ġk , Ġdistance ) Ċ } Ċ Ċ /** Ċ Ġ* ĠK - nearest Ġneighbor Ġclassifier Ġwith ĠE uclidean Ġdistance Ġas Ġthe Ġsimilarity Ġmeasure . Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġtraining Ġsamples . Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ġin Ġ[ 0 , Ġc ), Ġwhere Ġc Ġis Ġthe Ġnumber Ġof Ġclasses . Ċ Ġ* Ġ@ param Ġk Ġthe Ġnumber Ġof Ġneighbors Ġfor Ġclassification . Ċ Ġ*/ Ċ fun Ġk nn ( x : ĠArray < Double Array >, Ġy : ĠInt Array , Ġk : ĠInt ): ĠK NN < Double Array > Ġ{ ĊĠĠĠ Ġreturn ĠK NN . fit ( x , Ġy , Ġk ) Ċ } Ċ Ċ /** Ċ Ġ* ĠLog istic Ġregression . Ċ Ġ* ĠLog istic Ġregression Ġ( log it Ġmodel ) Ġis Ġa Ġgeneral ized Ċ Ġ* Ġlinear Ġmodel Ġused Ġfor Ġbin omial Ġregression . ĠLog istic Ġregression Ġapplies Ċ Ġ* Ġmaximum Ġlikelihood Ġestimation Ġafter Ġtransform ing Ġthe Ġdependent Ġinto Ċ Ġ* Ġa Ġlog it Ġvariable . ĠA Ġlog it Ġis Ġthe Ġnatural Ġlog Ġof Ġthe Ġodd s Ġof Ġthe Ġdependent Ċ Ġ* Ġequal ing Ġa Ġcertain Ġvalue Ġor Ġnot Ġ( usually Ġ 1 Ġin Ġbinary Ġlogist ic Ġmodels , Ċ Ġ* Ġthe Ġhighest Ġvalue Ġin Ġmult in omial Ġmodels ). ĠIn Ġthis Ġway , Ġlogist ic Ġregression Ċ Ġ* Ġestimates Ġthe Ġodd s Ġof Ġa Ġcertain Ġevent Ġ( value ) Ġoccur ring . Ċ Ġ* Ċ Ġ* ĠGood ness - of - fit Ġtests Ġsuch Ġas Ġthe Ġlikelihood Ġratio Ġtest Ġare Ġavailable Ċ Ġ* Ġas Ġindicators Ġof Ġmodel Ġappro pri aten ess , Ġas Ġis Ġthe ĠW ald Ġstatistic Ġto Ġtest Ċ Ġ* Ġthe Ġsignific ance Ġof Ġindividual Ġindependent Ġvariables . Ċ Ġ* Ċ Ġ* ĠLog istic Ġregression Ġhas Ġmany Ġanalog ies Ġto Ġordinary Ġleast Ġsquares Ġ( OL S ) Ċ Ġ* Ġregression . ĠUn like ĠO LS Ġregression , Ġhowever , Ġlogist ic Ġregression Ġdoes Ġnot Ċ Ġ* Ġassume Ġlinear ity Ġof Ġrelationship Ġbetween Ġthe Ġraw Ġvalues Ġof Ġthe Ġindependent Ċ Ġ* Ġvariables Ġand Ġthe Ġdependent , Ġdoes Ġnot Ġrequire Ġnormally Ġdistributed Ġvariables , Ċ Ġ* Ġdoes Ġnot Ġassume Ġhom os ced astic ity , Ġand Ġin Ġgeneral Ġhas Ġless Ġstring ent Ċ Ġ* Ġrequirements . Ċ Ġ* Ċ Ġ* ĠComp ared Ġwith Ġlinear Ġdis crimin ant Ġanalysis , Ġlogist ic Ġregression Ġhas Ġseveral Ċ Ġ* Ġadv antages : Ċ Ġ* Ċ Ġ* Ġ Ġ- ĠIt Ġis Ġmore Ġrobust : Ġthe Ġindependent Ġvariables Ġdon 't Ġhave Ġto Ġbe Ġnormally Ċ Ġ* ĠĠĠ Ġdistributed , Ġor Ġhave Ġequal Ġvariance Ġin Ġeach Ġgroup Ċ Ġ* Ċ Ġ* Ġ Ġ- ĠIt Ġdoes Ġnot Ġassume Ġa Ġlinear Ġrelationship Ġbetween Ġthe Ġindependent Ċ Ġ* ĠĠĠ Ġvariables Ġand Ġdependent Ġvariable . Ċ Ġ* Ċ Ġ* Ġ Ġ- ĠIt Ġmay Ġhandle Ġnonlinear Ġeffects Ġsince Ġone Ġcan Ġadd Ġexplicit Ġinteraction Ċ Ġ* ĠĠĠ Ġand Ġpower Ġterms . Ċ Ġ* Ċ Ġ* ĠHowever , Ġit Ġrequires Ġmuch Ġmore Ġdata Ġto Ġachieve Ġstable , Ġmeaningful Ġresults . Ċ Ġ* Ċ Ġ* ĠLog istic Ġregression Ġalso Ġhas Ġstrong Ġconnections Ġwith Ġneural Ġnetwork Ġand Ċ Ġ* Ġmaximum Ġentropy Ġmodeling . ĠFor Ġexample , Ġbinary Ġlogist ic Ġregression Ġis Ċ Ġ* Ġequivalent Ġto Ġa Ġone - layer , Ġsingle - output Ġneural Ġnetwork Ġwith Ġa Ġlogist ic Ċ Ġ* Ġactivation Ġfunction Ġtrained Ġunder Ġlog Ġloss . ĠSimilar ly , Ġmult in omial Ġlogist ic Ċ Ġ* Ġregression Ġis Ġequivalent Ġto Ġa Ġone - layer , Ġsoft max - output Ġneural Ġnetwork . Ċ Ġ* Ċ Ġ* ĠLog istic Ġregression Ġestimation Ġalso Ġo be ys Ġthe Ġmaximum Ġentropy Ġprinciple , Ġand Ċ Ġ* Ġthus Ġlogist ic Ġregression Ġis Ġsometimes Ġcalled Ġ" maximum Ġentropy Ġmodeling ", Ċ Ġ* Ġand Ġthe Ġresulting Ġclassifier Ġthe Ġ" maximum Ġentropy Ġclassifier ". Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġtraining Ġsamples . Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ġin Ġ[ 0 , Ġk ), Ġwhere Ġk Ġis Ġthe Ġnumber Ġof Ġclasses . Ċ Ġ* Ġ@ param Ġlambda Ġ& lambda ; Ġ& gt ; Ġ 0 Ġgives Ġa Ġ" regular ized " Ġestimate Ġof Ġlinear Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġweights Ġwhich Ġoften Ġhas Ġsuperior Ġgeneral ization Ġperformance , Ġespecially Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġthe Ġdimension ality Ġis Ġhigh . Ċ Ġ* Ġ@ param Ġtol Ġthe Ġtolerance Ġfor Ġstopping Ġiterations . Ċ Ġ* Ġ@ param Ġmax Iter Ġthe Ġmaximum Ġnumber Ġof Ġiterations . Ċ Ġ* Ċ Ġ* Ġ@ return ĠLog istic Ġregression Ġmodel . Ċ Ġ*/ Ċ fun Ġlog it ( x : ĠArray < Double Array >, Ġy : ĠInt Array , Ġlambda : ĠDouble Ġ= Ġ 0 . 0 , Ġtol : ĠDouble Ġ= Ġ 1 E - 5 , Ġmax Iter : ĠInt Ġ= Ġ 5 0 0 ): ĠLog istic Regression Ġ{ ĊĠĠĠ Ġreturn ĠLog istic Regression . fit ( x , Ġy , Ġlambda , Ġtol , Ġmax Iter ) Ċ } Ċ Ċ /** Ċ Ġ* ĠMaximum Ġentropy Ġclassifier . Ċ Ġ* ĠMaximum Ġentropy Ġis Ġa Ġtechnique Ġfor Ġlearning Ċ Ġ* Ġprobability Ġdistributions Ġfrom Ġdata . ĠIn Ġmaximum Ġentropy Ġmodels , Ġthe Ċ Ġ* Ġobserved Ġdata Ġitself Ġis Ġassumed Ġto Ġbe Ġthe Ġtest able Ġinformation . ĠMaximum Ċ Ġ* Ġentropy Ġmodels Ġdon 't Ġassume Ġanything Ġabout Ġthe Ġprobability Ġdistribution Ċ Ġ* Ġother Ġthan Ġwhat Ġhave Ġbeen Ġobserved Ġand Ġalways Ġchoose Ġthe Ġmost Ġuniform Ċ Ġ* Ġdistribution Ġsubject Ġto Ġthe Ġobserved Ġconstraints . Ċ Ġ* Ċ Ġ* ĠBasic ally , Ġmaximum Ġentropy Ġclassifier Ġis Ġanother Ġname Ġof Ġmult in omial Ġlogist ic Ċ Ġ* Ġregression Ġapplied Ġto Ġcategorical Ġindependent Ġvariables , Ġwhich Ġare Ċ Ġ* Ġconverted Ġto Ġbinary Ġdummy Ġvariables . ĠMaximum Ġentropy Ġmodels Ġare Ġwidely Ċ Ġ* Ġused Ġin Ġnatural Ġlanguage Ġprocessing . Ġ ĠHere , Ġwe Ġprovide Ġan Ġimplementation Ċ Ġ* Ġwhich Ġassumes Ġthat Ġbinary Ġfeatures Ġare Ġstored Ġin Ġa Ġsparse Ġarray , Ġof Ġwhich Ċ Ġ* Ġentries Ġare Ġthe Ġindices Ġof Ġnon zero Ġfeatures . Ċ Ġ* Ċ Ġ* Ġ=== = References : ==== Ċ Ġ* Ġ Ġ- ĠA . ĠL . ĠBer ger , ĠS . ĠD . ĠP ie tra , Ġand ĠV . ĠJ . ĠD . ĠP ie tra . ĠA Ġmaximum Ġentropy Ġapproach Ġto Ġnatural Ġlanguage Ġprocessing . ĠComput ational ĠL ingu istics Ġ 2 2 ( 1 ): 3 9 - 7 1 , Ġ 1 9 9 6 . Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġtraining Ġsamples . ĠEach Ġsample Ġis Ġrepresented Ġby Ġa Ġset Ġof Ġsparse Ċ Ġ* ĠĠĠĠĠĠĠĠĠ Ġbinary Ġfeatures . ĠThe Ġfeatures Ġare Ġstored Ġin Ġan Ġinteger Ġarray , Ġof Ġwhich Ċ Ġ* ĠĠĠĠĠĠĠĠĠ Ġare Ġthe Ġindices Ġof Ġnon zero Ġfeatures . Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ġin Ġ[ 0 , Ġk ), Ġwhere Ġk Ġis Ġthe Ġnumber Ġof Ġclasses . Ċ Ġ* Ġ@ param Ġp Ġthe Ġdimension Ġof Ġfeature Ġspace . Ċ Ġ* Ġ@ param Ġlambda Ġ& lambda ; Ġ& gt ; Ġ 0 Ġgives Ġa Ġ" regular ized " Ġestimate Ġof Ġlinear Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġweights Ġwhich Ġoften Ġhas Ġsuperior Ġgeneral ization Ġperformance , Ġespecially Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġthe Ġdimension ality Ġis Ġhigh . Ċ Ġ* Ġ@ param Ġtol Ġtolerance Ġfor Ġstopping Ġiterations . Ċ Ġ* Ġ@ param Ġmax Iter Ġmaximum Ġnumber Ġof Ġiterations . Ċ Ġ* Ġ@ return ĠMaximum Ġentropy Ġmodel . Ċ Ġ*/ Ċ fun Ġmax ent ( x : ĠArray < IntArray >, Ġy : ĠInt Array , Ġp : ĠInt , Ġlambda : ĠDouble Ġ= Ġ 0 . 1 , Ġtol : ĠDouble Ġ= Ġ 1 E - 5 , Ġmax Iter : ĠInt Ġ= Ġ 5 0 0 ): ĠMax ent Ġ{ ĊĠĠĠ Ġreturn ĠMax ent . fit ( p , Ġx , Ġy , Ġlambda , Ġtol , Ġmax Iter ) Ċ } Ċ Ċ /** Ċ Ġ* ĠMult il ayer Ġper ce ptr on Ġneural Ġnetwork . Ċ Ġ* ĠAn ĠM LP Ġconsists Ġof Ġseveral Ġlayers Ġof Ġnodes , Ġinter connected Ġthrough Ġweighted Ċ Ġ* Ġac yc lic Ġar cs Ġfrom Ġeach Ġpreceding Ġlayer Ġto Ġthe Ġfollowing , Ġwithout Ġlater al Ġor Ċ Ġ* Ġfeedback Ġconnections . ĠEach Ġnode Ġcalculates Ġa Ġtransformed Ġweighted Ġlinear Ċ Ġ* Ġcombination Ġof Ġits Ġinputs Ġ( output Ġactiv ations Ġfrom Ġthe Ġpreceding Ġlayer ), Ġwith Ċ Ġ* Ġone Ġof Ġthe Ġweights Ġact ing Ġas Ġa Ġtrain able Ġbias Ġconnected Ġto Ġa Ġconstant Ġinput . Ċ Ġ* ĠThe Ġtransformation , Ġcalled Ġactivation Ġfunction , Ġis Ġa Ġbounded Ġnon - de creasing Ċ Ġ* Ġ( non - linear ) Ġfunction , Ġsuch Ġas Ġthe Ġsig moid Ġfunctions Ġ( ranges Ġfrom Ġ 0 Ġto Ġ 1 ). Ċ Ġ* ĠAnother Ġpopular Ġactivation Ġfunction Ġis Ġhyper b olic Ġtangent Ġwhich Ġis Ġactually Ċ Ġ* Ġequivalent Ġto Ġthe Ġsig moid Ġfunction Ġin Ġshape Ġbut Ġranges Ġfrom Ġ- 1 Ġto Ġ 1 . Ċ Ġ* ĠMore Ġspecialized Ġactivation Ġfunctions Ġinclude Ġradial Ġbasis Ġfunctions Ġwhich Ċ Ġ* Ġare Ġused Ġin ĠR BF Ġnetworks . Ċ Ġ* Ċ Ġ* ĠThe Ġrepresent ational Ġcapabilities Ġof Ġa ĠM LP Ġare Ġdetermined Ġby Ġthe Ġrange Ġof Ċ Ġ* Ġmappings Ġit Ġmay Ġimplement Ġthrough Ġweight Ġvariation . ĠSingle Ġlayer Ġper ce ptr ons Ċ Ġ* Ġare Ġcapable Ġof Ġsolving Ġonly Ġlinear ly Ġsepar able Ġproblems . ĠWith Ġthe Ġsig moid Ċ Ġ* Ġfunction Ġas Ġactivation Ġfunction , Ġthe Ġsingle - layer Ġnetwork Ġis Ġidentical Ċ Ġ* Ġto Ġthe Ġlogist ic Ġregression Ġmodel . Ċ Ġ* Ċ Ġ* ĠThe Ġuniversal Ġapproximation Ġthe orem Ġfor Ġneural Ġnetworks Ġstates Ġthat Ġevery Ċ Ġ* Ġcontinuous Ġfunction Ġthat Ġmaps Ġintervals Ġof Ġreal Ġnumbers Ġto Ġsome Ġoutput Ċ Ġ* Ġinterval Ġof Ġreal Ġnumbers Ġcan Ġbe Ġapprox imated Ġar bitr arily Ġclosely Ġby Ġa Ċ Ġ* Ġmulti - layer Ġper ce ptr on Ġwith Ġjust Ġone Ġhidden Ġlayer . ĠThis Ġresult Ġholds Ġonly Ċ Ġ* Ġfor Ġrestricted Ġclasses Ġof Ġactivation Ġfunctions , Ġwhich Ġare Ġextremely Ġcomplex Ċ Ġ* Ġand ĠNOT Ġsmooth Ġfor Ġsub tle Ġmathematical Ġreasons . ĠOn Ġthe Ġother Ġhand , Ġsmooth ness Ċ Ġ* Ġis Ġimportant Ġfor Ġgradient Ġdesc ent Ġlearning . ĠBes ides , Ġthe Ġproof Ġis Ġnot Ċ Ġ* Ġconstruct ive Ġregarding Ġthe Ġnumber Ġof Ġne urons Ġrequired Ġor Ġthe Ġsettings Ġof Ċ Ġ* Ġthe Ġweights . ĠTherefore , Ġcomplex Ġsystems Ġwill Ġhave Ġmore Ġlayers Ġof Ġne urons Ċ Ġ* Ġwith Ġsome Ġhaving Ġincreased Ġlayers Ġof Ġinput Ġne urons Ġand Ġoutput Ġne urons Ċ Ġ* Ġin Ġpractice . Ċ Ġ* Ċ Ġ* ĠThe Ġmost Ġpopular Ġalgorithm Ġto Ġtrain ĠM LP s Ġis Ġback - propagation , Ġwhich Ġis Ġa Ċ Ġ* Ġgradient Ġdesc ent Ġmethod . ĠBased Ġon Ġchain Ġrule , Ġthe Ġalgorithm Ġpropag ates Ġthe Ċ Ġ* Ġerror Ġback Ġthrough Ġthe Ġnetwork Ġand Ġadjust s Ġthe Ġweights Ġof Ġeach Ġconnection Ġin Ċ Ġ* Ġorder Ġto Ġreduce Ġthe Ġvalue Ġof Ġthe Ġerror Ġfunction Ġby Ġsome Ġsmall Ġamount . Ċ Ġ* ĠFor Ġthis Ġreason , Ġback - propagation Ġcan Ġonly Ġbe Ġapplied Ġon Ġnetworks Ġwith Ċ Ġ* Ġdifferent iable Ġactivation Ġfunctions . Ċ Ġ* Ċ Ġ* ĠDuring Ġerror Ġback Ġpropagation , Ġwe Ġusually Ġtimes Ġthe Ġgradient Ġwith Ġa Ġsmall Ċ Ġ* Ġnumber Ġ& eta ;, Ġcalled Ġlearning Ġrate , Ġwhich Ġis Ġcarefully Ġselected Ġto Ġensure Ċ Ġ* Ġthat Ġthe Ġnetwork Ġconver ges Ġto Ġa Ġlocal Ġminimum Ġof Ġthe Ġerror Ġfunction Ċ Ġ* Ġfast Ġenough , Ġwithout Ġproducing Ġosc ill ations . ĠOne Ġway Ġto Ġavoid Ġosc ill ation Ċ Ġ* Ġat Ġlarge Ġ& eta ;, Ġis Ġto Ġmake Ġthe Ġchange Ġin Ġweight Ġdependent Ġon Ġthe Ġpast Ġweight Ċ Ġ* Ġchange Ġby Ġadding Ġa Ġmomentum Ġterm . Ċ Ġ* Ċ Ġ* ĠAlthough Ġthe Ġback - propagation Ġalgorithm Ġmay Ġperforms Ġgradient Ċ Ġ* Ġdesc ent Ġon Ġthe Ġtotal Ġerror Ġof Ġall Ġinstances Ġin Ġa Ġbatch Ġway , Ċ Ġ* Ġthe Ġlearning Ġrule Ġis Ġoften Ġapplied Ġto Ġeach Ġinstance Ġseparately Ġin Ġan Ġonline Ċ Ġ* Ġway Ġor Ġst och astic Ġway . ĠThere Ġexists Ġemp irical Ġindication Ġthat Ġthe Ġst och astic Ċ Ġ* Ġway Ġresults Ġin Ġfaster Ġconvergence . Ċ Ġ* Ċ Ġ* ĠIn Ġpractice , Ġthe Ġproblem Ġof Ġover - fitting Ġhas Ġem erge d . ĠThis Ġar ises Ġin Ċ Ġ* Ġcon vol uted Ġor Ġover - specified Ġsystems Ġwhen Ġthe Ġcapacity Ġof Ġthe Ġnetwork Ċ Ġ* Ġsignificantly Ġexceeds Ġthe Ġneeded Ġfree Ġparameters . ĠThere Ġare Ġtwo Ġgeneral Ċ Ġ* Ġapproaches Ġfor Ġavoid ing Ġthis Ġproblem : ĠThe Ġfirst Ġis Ġto Ġuse Ġcross - validation Ċ Ġ* Ġand Ġsimilar Ġtechniques Ġto Ġcheck Ġfor Ġthe Ġpresence Ġof Ġover - fitting Ġand Ċ Ġ* Ġoptim ally Ġselect Ġhyper - parameters Ġsuch Ġas Ġto Ġminimize Ġthe Ġgeneral ization Ċ Ġ* Ġerror . ĠThe Ġsecond Ġis Ġto Ġuse Ġsome Ġform Ġof Ġregular ization , Ġwhich Ġem erge s Ċ Ġ* Ġn atur ally Ġin Ġa ĠBay esian Ġframework , Ġwhere Ġthe Ġregular ization Ġcan Ġbe Ċ Ġ* Ġperformed Ġby Ġselecting Ġa Ġlarger Ġprior Ġprobability Ġover Ġsimpler Ġmodels ; Ċ Ġ* Ġbut Ġalso Ġin Ġstatistical Ġlearning Ġtheory , Ġwhere Ġthe Ġgoal Ġis Ġto Ġminimize Ġover Ċ Ġ* Ġthe Ġ" emp irical Ġrisk " Ġand Ġthe Ġ" struct ural Ġrisk ". Ċ Ġ* Ċ Ġ* ĠFor Ġneural Ġnetworks , Ġthe Ġinput Ġpatterns Ġusually Ġshould Ġbe Ġscaled / standard ized . Ċ Ġ* ĠCommon ly , Ġeach Ġinput Ġvariable Ġis Ġscaled Ġinto Ġinterval Ġ`[ 0 , Ġ 1 ]` Ġor Ġto Ġhave Ċ Ġ* Ġmean Ġ 0 Ġand Ġstandard Ġdeviation Ġ 1 . Ċ Ġ* Ċ Ġ* ĠFor Ġpenalty Ġfunctions Ġand Ġoutput Ġunits , Ġthe Ġfollowing Ġnatural Ġpair ings Ġare Ċ Ġ* Ġrecommended : Ċ Ġ* Ċ Ġ* Ġ Ġ- Ġlinear Ġoutput Ġunits Ġand Ġa Ġleast Ġsquares Ġpenalty Ġfunction . Ċ Ġ* Ġ Ġ- Ġa Ġtwo - class Ġcross - entropy Ġpenalty Ġfunction Ġand Ġa Ġlogist ic Ċ Ġ* ĠĠĠ Ġactivation Ġfunction . Ċ Ġ* Ġ Ġ- Ġa Ġmulti - class Ġcross - entropy Ġpenalty Ġfunction Ġand Ġa Ġsoft max Ċ Ġ* ĠĠĠ Ġactivation Ġfunction . Ċ Ġ* Ċ Ġ* ĠBy Ġassigning Ġa Ġsoft max Ġactivation Ġfunction Ġon Ġthe Ġoutput Ġlayer Ġof Ċ Ġ* Ġthe Ġneural Ġnetwork Ġfor Ġcategorical Ġtarget Ġvariables , Ġthe Ġoutputs Ċ Ġ* Ġcan Ġbe Ġinterpreted Ġas Ġposterior Ġprobabilities , Ġwhich Ġare Ġvery Ġuseful . Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġtraining Ġsamples . Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ġin Ġ[ 0 , Ġk ), Ġwhere Ġk Ġis Ġthe Ġnumber Ġof Ġclasses . Ċ Ġ* Ġ@ param Ġbuild ers Ġthe Ġbuild ers Ġof Ġlayers Ġfrom Ġbottom Ġto Ġtop . Ċ Ġ* Ġ@ param Ġepochs Ġthe Ġnumber Ġof Ġepochs Ġof Ġst och astic Ġlearning . Ċ Ġ* Ġ@ param Ġlearning Rate Ġthe Ġlearning Ġrate . Ċ Ġ* Ġ@ param Ġmomentum Ġthe Ġmomentum Ġfactor . Ċ Ġ* Ġ@ param Ġweight Dec ay Ġthe Ġweight Ġdecay Ġfor Ġregular ization . Ċ Ġ* Ġ@ param Ġrho ĠThe ĠR MS Prop Ġdiscount ing Ġfactor Ġfor Ġthe Ġhistory / coming Ġgradient . Ċ Ġ* Ġ@ param Ġepsilon ĠA Ġsmall Ġconstant Ġfor ĠR MS Prop Ġnumerical Ġstability . Ċ Ġ*/ Ċ fun Ġm lp ( x : ĠArray < Double Array >, Ġy : ĠInt Array , Ġbuild ers : ĠArray < Layer Builder >, Ġepochs : ĠInt Ġ= Ġ 1 0 , ĊĠĠĠĠĠĠ Ġlearning Rate : ĠTime Function Ġ= ĠTime Function . linear ( 0 . 0 1 , Ġ 1 0 0 0 0 . 0 , Ġ 0 . 0 0 1 ), ĊĠĠĠĠĠĠ Ġmomentum : ĠTime Function Ġ= ĠTime Function . constant ( 0 . 0 ), ĊĠĠĠĠĠĠ Ġweight Dec ay : ĠDouble Ġ= Ġ 0 . 0 , Ġrho : ĠDouble Ġ= Ġ 0 . 0 , Ġepsilon : ĠDouble Ġ= Ġ 1 E - 7 ): ĠM LP Ġ{ ĊĠĠĠ Ġval Ġnet Ġ= ĠM LP ( x [ 0 ]. size , Ġ* builders ) ĊĠĠĠ Ġnet . set Learning Rate ( learning Rate ) ĊĠĠĠ Ġnet . set Moment um ( momentum ) ĊĠĠĠ Ġnet . set Weight Dec ay ( weight Dec ay ) ĊĠĠĠ Ġnet . set RMS Prop ( rho , Ġepsilon ) ĠĊĠĠĠ Ġfor Ġ( i Ġin Ġ 1 Ġ.. Ġepochs ) Ġnet . update ( x , Ġy ) ĊĠĠĠ Ġreturn Ġnet Ċ } Ċ Ċ /** Ċ Ġ* ĠRad ial Ġbasis Ġfunction Ġnetworks . Ċ Ġ* ĠA Ġradial Ġbasis Ġfunction Ġnetwork Ġis Ġan Ċ Ġ* Ġart ificial Ġneural Ġnetwork Ġthat Ġuses Ġradial Ġbasis Ġfunctions Ġas Ġactivation Ċ Ġ* Ġfunctions . ĠIt Ġis Ġa Ġlinear Ġcombination Ġof Ġradial Ġbasis Ġfunctions . ĠThey Ġare Ċ Ġ* Ġused Ġin Ġfunction Ġapproximation , Ġtime Ġseries Ġprediction , Ġand Ġcontrol . Ċ Ġ* Ċ Ġ* ĠIn Ġits Ġbasic Ġform , Ġradial Ġbasis Ġfunction Ġnetwork Ġis Ġin Ġthe Ġform Ċ Ġ* Ċ Ġ* Ġy ( x ) Ġ= Ġ& Sigma ; Ġw < sub > i </ sub > Ġ& phi ;( || x - c < sub > i </ sub > || ) Ċ Ġ* Ċ Ġ* Ġwhere Ġthe Ġapprox im ating Ġfunction Ġy ( x ) Ġis Ġrepresented Ġas Ġa Ġsum Ġof ĠN Ġradial Ċ Ġ* Ġbasis Ġfunctions Ġ& phi ;, Ġeach Ġassociated Ġwith Ġa Ġdifferent Ġcenter Ġc < sub > i </ sub >, Ċ Ġ* Ġand Ġweighted Ġby Ġan Ġappropriate Ġcoefficient Ġw < sub > i </ sub >. ĠFor Ġdistance , Ċ Ġ* Ġone Ġusually Ġch oo ses ĠE uclidean Ġdistance . ĠThe Ġweights Ġw < sub > i </ sub > Ġcan Ċ Ġ* Ġbe Ġestimated Ġusing Ġthe Ġmatrix Ġmethods Ġof Ġlinear Ġleast Ġsquares , Ġbecause Ċ Ġ* Ġthe Ġapprox im ating Ġfunction Ġis Ġlinear Ġin Ġthe Ġweights . Ċ Ġ* Ċ Ġ* ĠThe Ġcenters Ġc < sub > i </ sub > Ġcan Ġbe Ġrandomly Ġselected Ġfrom Ġtraining Ġdata , Ċ Ġ* Ġor Ġlearned Ġby Ġsome Ġclustering Ġmethod Ġ( e . g . Ġk - means ), Ġor Ġlearned Ġtogether Ċ Ġ* Ġwith Ġweight Ġparameters Ġunder go Ġa Ġsuper vised Ġlearning Ġprocessing Ċ Ġ* Ġ( e . g . Ġerror - correction Ġlearning ). Ċ Ġ* Ċ Ġ* ĠThe Ġpopular Ġchoices Ġfor Ġ& phi ; Ġcomp rise Ġthe ĠGaussian Ġfunction Ġand Ġthe Ġso Ċ Ġ* Ġcalled Ġthin Ġplate Ġspl ines . ĠThe Ġadvantage Ġof Ġthe Ġthin Ġplate Ġspl ines Ġis Ġthat Ċ Ġ* Ġtheir Ġcondition ing Ġis Ġinvariant Ġunder Ġscal ings . ĠGaussian , Ġmulti - quad ric Ċ Ġ* Ġand Ġinverse Ġmulti - quad ric Ġare Ġinf initely Ġsmooth Ġand Ġand Ġinvolve Ġa Ġscale Ċ Ġ* Ġor Ġshape Ġparameter , Ġr < sub >< small > 0 </ small ></ sub > Ġ& gt ; Ġ 0 . ĠDec re asing Ċ Ġ* Ġr < sub >< small > 0 </ small ></ sub > Ġt ends Ġto Ġflatten Ġthe Ġbasis Ġfunction . ĠFor Ġa Ċ Ġ* Ġgiven Ġfunction , Ġthe Ġquality Ġof Ġapproximation Ġmay Ġstrongly Ġdepend Ġon Ġthis Ċ Ġ* Ġparameter . ĠIn Ġparticular , Ġincreasing Ġr < sub >< small > 0 </ small ></ sub > Ġhas Ġthe Ċ Ġ* Ġeffect Ġof Ġbetter Ġcondition ing Ġ( the Ġseparation Ġdistance Ġof Ġthe Ġscaled Ġpoints Ċ Ġ* Ġincreases ). Ċ Ġ* Ċ Ġ* ĠA Ġvariant Ġon ĠR BF Ġnetworks Ġis Ġnormalized Ġradial Ġbasis Ġfunction Ġ( NR BF ) Ċ Ġ* Ġnetworks , Ġin Ġwhich Ġwe Ġrequire Ġthe Ġsum Ġof Ġthe Ġbasis Ġfunctions Ġto Ġbe Ġun ity . Ċ Ġ* ĠNR BF Ġar ises Ġmore Ġn atur ally Ġfrom Ġa ĠBay esian Ġstatistical Ġperspective . ĠHowever , Ċ Ġ* Ġthere Ġis Ġno Ġevidence Ġthat Ġeither Ġthe ĠNR BF Ġmethod Ġis Ġconsistently Ġsuperior Ċ Ġ* Ġto Ġthe ĠR BF Ġmethod , Ġor Ġvice Ġvers a . Ċ Ġ* Ċ Ġ* ĠS VM s Ġwith ĠGaussian Ġkernel Ġhave Ġsimilar Ġstructure Ġas ĠR BF Ġnetworks Ġwith Ċ Ġ* ĠGaussian Ġradial Ġbasis Ġfunctions . ĠHowever , Ġthe ĠS VM Ġapproach Ġ" autom atically " Ċ Ġ* Ġsolves Ġthe Ġnetwork Ġcomplexity Ġproblem Ġsince Ġthe Ġsize Ġof Ġthe Ġhidden Ġlayer Ċ Ġ* Ġis Ġobtained Ġas Ġthe Ġresult Ġof Ġthe ĠQ P Ġprocedure . ĠHidden Ġne urons Ġand Ċ Ġ* Ġsupport Ġvectors Ġcorrespond Ġto Ġeach Ġother , Ġso Ġthe Ġcenter Ġproblems Ġof Ċ Ġ* Ġthe ĠR BF Ġnetwork Ġis Ġalso Ġsolved , Ġas Ġthe Ġsupport Ġvectors Ġserve Ġas Ġthe Ċ Ġ* Ġbasis Ġfunction Ġcenters . ĠIt Ġwas Ġreported Ġthat Ġwith Ġsimilar Ġnumber Ġof Ġsupport Ċ Ġ* Ġvectors / centers , ĠS VM Ġshows Ġbetter Ġgeneral ization Ġperformance Ġthan ĠR BF Ċ Ġ* Ġnetwork Ġwhen Ġthe Ġtraining Ġdata Ġsize Ġis Ġrelatively Ġsmall . ĠOn Ġthe Ġother Ġhand , Ċ Ġ* ĠR BF Ġnetwork Ġgives Ġbetter Ġgeneral ization Ġperformance Ġthan ĠS VM Ġon Ġlarge Ċ Ġ* Ġtraining Ġdata . Ċ Ġ* Ċ Ġ* Ġ=== = References : ==== Ċ Ġ* Ġ Ġ- ĠSimon ĠH ay kin . ĠNeural ĠNetworks : ĠA ĠComp reh ensive ĠFoundation Ġ( 2 nd Ġedition ). Ġ 1 9 9 9 . Ċ Ġ* Ġ Ġ- ĠT . ĠP ogg io Ġand ĠF . ĠG iro si . ĠNetworks Ġfor Ġapproximation Ġand Ġlearning . ĠProc . ĠIEEE Ġ 7 8 ( 9 ): 1 4 8 4 - 1 4 8 7 , Ġ 1 9 9 0 . Ċ Ġ* Ġ Ġ- ĠN abil ĠBen oud jit Ġand ĠM ic hel ĠVer le ys en . ĠOn Ġthe Ġkernel Ġwidths Ġin Ġradial - basis Ġfunction Ġnetworks . ĠNeural ĠProcess , Ġ 2 0 0 3 . Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġtraining Ġsamples . Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ġin Ġ[ 0 , Ġk ), Ġwhere Ġk Ġis Ġthe Ġnumber Ġof Ġclasses . Ċ Ġ* Ġ@ param Ġne urons Ġthe Ġradial Ġbasis Ġfunctions . Ċ Ġ* Ġ@ param Ġnormalized Ġtrain Ġa Ġnormalized ĠR BF Ġnetwork Ġor Ġnot . Ċ Ġ*/ Ċ fun Ġ< T > Ġr bf net ( x : ĠArray < T >, Ġy : ĠInt Array , Ġne urons : ĠArray < R BF < T >>, Ġnormalized : ĠBoolean Ġ= Ġfalse ): ĠR BF Network < T > Ġ{ ĊĠĠĠ Ġreturn ĠR BF Network . fit ( x , Ġy , Ġne urons , Ġnormalized ) Ċ } Ċ Ċ /** ĠTr ains Ġa ĠGaussian ĠR BF Ġnetwork Ġwith Ġk - means . Ġ*/ Ċ fun Ġr bf net ( x : ĠArray < Double Array >, Ġy : ĠInt Array , Ġk : ĠInt , Ġnormalized : ĠBoolean Ġ= Ġfalse ): ĠR BF Network < Double Array > Ġ{ ĊĠĠĠ Ġval Ġne urons Ġ= ĠR BF . fit ( x , Ġk ) ĊĠĠĠ Ġreturn ĠR BF Network . fit ( x , Ġy , Ġne urons , Ġnormalized ) Ċ } Ċ Ċ /** Ċ Ġ* ĠSupport Ġvector Ġmachines Ġfor Ġclassification . ĠThe Ġbasic Ġsupport Ġvector Ġmachine Ċ Ġ* Ġis Ġa Ġbinary Ġlinear Ġclassifier Ġwhich Ġch oo ses Ġthe Ġhyper plane Ġthat Ġrepresents Ċ Ġ* Ġthe Ġlargest Ġseparation , Ġor Ġmargin , Ġbetween Ġthe Ġtwo Ġclasses . ĠIf Ġsuch Ġa Ċ Ġ* Ġhyper plane Ġexists , Ġit Ġis Ġknown Ġas Ġthe Ġmaximum - margin Ġhyper plane Ġand Ġthe Ċ Ġ* Ġlinear Ġclassifier Ġit Ġdefines Ġis Ġknown Ġas Ġa Ġmaximum Ġmargin Ġclassifier . Ċ Ġ* Ċ Ġ* ĠIf Ġthere Ġexists Ġno Ġhyper plane Ġthat Ġcan Ġperfectly Ġsplit Ġthe Ġpositive Ġand Ċ Ġ* Ġnegative Ġinstances , Ġthe Ġsoft Ġmargin Ġmethod Ġwill Ġchoose Ġa Ġhyper plane Ċ Ġ* Ġthat Ġsplits Ġthe Ġinstances Ġas Ġclean ly Ġas Ġpossible , Ġwhile Ġstill Ġmaxim izing Ċ Ġ* Ġthe Ġdistance Ġto Ġthe Ġnearest Ġclean ly Ġsplit Ġinstances . Ċ Ġ* Ċ Ġ* ĠThe Ġnonlinear ĠS VM s Ġare Ġcreated Ġby Ġapplying Ġthe Ġkernel Ġtrick Ġto Ċ Ġ* Ġmaximum - margin Ġhyper planes . ĠThe Ġresulting Ġalgorithm Ġis Ġform ally Ġsimilar , Ċ Ġ* Ġexcept Ġthat Ġevery Ġdot Ġproduct Ġis Ġreplaced Ġby Ġa Ġnonlinear Ġkernel Ġfunction . Ċ Ġ* ĠThis Ġallows Ġthe Ġalgorithm Ġto Ġfit Ġthe Ġmaximum - margin Ġhyper plane Ġin Ġa Ċ Ġ* Ġtransformed Ġfeature Ġspace . ĠThe Ġtransformation Ġmay Ġbe Ġnonlinear Ġand Ċ Ġ* Ġthe Ġtransformed Ġspace Ġbe Ġhigh Ġdimensional . ĠFor Ġexample , Ġthe Ġfeature Ġspace Ċ Ġ* Ġcorresponding ĠGaussian Ġkernel Ġis Ġa ĠH il bert Ġspace Ġof Ġinfinite Ġdimension . Ċ Ġ* ĠThus Ġthough Ġthe Ġclassifier Ġis Ġa Ġhyper plane Ġin Ġthe Ġhigh - dimensional Ġfeature Ċ Ġ* Ġspace , Ġit Ġmay Ġbe Ġnonlinear Ġin Ġthe Ġoriginal Ġinput Ġspace . ĠMaximum Ġmargin Ċ Ġ* Ġclassifiers Ġare Ġwell Ġregular ized , Ġso Ġthe Ġinfinite Ġdimension Ġdoes Ġnot Ġspo il Ċ Ġ* Ġthe Ġresults . Ċ Ġ* Ċ Ġ* ĠThe Ġeffect iveness Ġof ĠS VM Ġdepends Ġon Ġthe Ġselection Ġof Ġkernel , Ġthe Ġkernel 's Ċ Ġ* Ġparameters , Ġand Ġsoft Ġmargin Ġparameter ĠC . ĠGiven Ġa Ġkernel , Ġbest Ġcombination Ċ Ġ* Ġof ĠC Ġand Ġkernel 's Ġparameters Ġis Ġoften Ġselected Ġby Ġa Ġgrid - search Ġwith Ċ Ġ* Ġcross Ġvalidation . Ċ Ġ* Ċ Ġ* ĠThe Ġdom inant Ġapproach Ġfor Ġcreating Ġmulti - class ĠS VM s Ġis Ġto Ġreduce Ġthe Ċ Ġ* Ġsingle Ġmulti - class Ġproblem Ġinto Ġmultiple Ġbinary Ġclassification Ġproblems . Ċ Ġ* ĠCommon Ġmethods Ġfor Ġsuch Ġreduction Ġis Ġto Ġbuild Ġbinary Ġclassifiers Ġwhich Ċ Ġ* Ġdistinguish Ġbetween Ġ( i ) Ġone Ġof Ġthe Ġlabels Ġto Ġthe Ġrest Ġ( one - vers us - all ) Ċ Ġ* Ġor Ġ( ii ) Ġbetween Ġevery Ġpair Ġof Ġclasses Ġ( one - vers us - one ). ĠClassification Ċ Ġ* Ġof Ġnew Ġinstances Ġfor Ġone - vers us - all Ġcase Ġis Ġdone Ġby Ġa Ġwinner - t akes - all Ċ Ġ* Ġstrategy , Ġin Ġwhich Ġthe Ġclassifier Ġwith Ġthe Ġhighest Ġoutput Ġfunction Ġassigns Ċ Ġ* Ġthe Ġclass . ĠFor Ġthe Ġone - vers us - one Ġapproach , Ġclassification Ċ Ġ* Ġis Ġdone Ġby Ġa Ġmax - wins Ġvoting Ġstrategy , Ġin Ġwhich Ġevery Ġclassifier Ġassigns Ċ Ġ* Ġthe Ġinstance Ġto Ġone Ġof Ġthe Ġtwo Ġclasses , Ġthen Ġthe Ġvote Ġfor Ġthe Ġassigned Ċ Ġ* Ġclass Ġis Ġincreased Ġby Ġone Ġvote , Ġand Ġfinally Ġthe Ġclass Ġwith Ġmost Ġvotes Ċ Ġ* Ġdetermines Ġthe Ġinstance Ġclassification . Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġtraining Ġdata Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ċ Ġ* Ġ@ param Ġkernel ĠM erc er Ġkernel Ċ Ġ* Ġ@ param ĠC Ġthe Ġregular ization Ġparameter Ċ Ġ* Ġ@ param Ġtol Ġthe Ġtolerance Ġof Ġconvergence Ġtest . Ċ Ġ* Ġ@ tparam ĠT Ġthe Ġdata Ġtype Ċ Ġ* Ċ Ġ* Ġ@ return ĠS VM Ġmodel . Ċ Ġ*/ Ċ fun Ġ< T > Ġsvm ( x : ĠArray < T >, Ġy : ĠInt Array , Ġkernel : ĠM erc er Kernel < T >, ĠC : ĠDouble , Ġtol : ĠDouble Ġ= Ġ 1 E - 3 ): ĠS VM < T > Ġ{ ĊĠĠĠ Ġreturn ĠS VM . fit ( x , Ġy , Ġkernel , ĠC , Ġtol ) Ċ } Ċ Ċ /** Ċ Ġ* ĠDecision Ġtree . ĠA Ġclassification / regression Ġtree Ġcan Ġbe Ġlearned Ġby Ċ Ġ* Ġsplitting Ġthe Ġtraining Ġset Ġinto Ġsub sets Ġbased Ġon Ġan Ġattribute Ġvalue Ċ Ġ* Ġtest . ĠThis Ġprocess Ġis Ġrepeated Ġon Ġeach Ġderived Ġsubset Ġin Ġa Ġrecursive Ċ Ġ* Ġmanner Ġcalled Ġrecursive Ġpartition ing . ĠThe Ġrecursion Ġis Ġcompleted Ġwhen Ċ Ġ* Ġthe Ġsubset Ġat Ġa Ġnode Ġall Ġhas Ġthe Ġsame Ġvalue Ġof Ġthe Ġtarget Ġvariable , Ċ Ġ* Ġor Ġwhen Ġsplitting Ġno Ġlonger Ġadds Ġvalue Ġto Ġthe Ġpredictions . Ċ Ġ* Ċ Ġ* ĠThe Ġalgorithms Ġthat Ġare Ġused Ġfor Ġconstructing Ġdecision Ġtrees Ġusually Ċ Ġ* Ġwork Ġtop - down Ġby Ġchoosing Ġa Ġvariable Ġat Ġeach Ġstep Ġthat Ġis Ġthe Ġnext Ġbest Ċ Ġ* Ġvariable Ġto Ġuse Ġin Ġsplitting Ġthe Ġset Ġof Ġitems . Ġ" Best " Ġis Ġdefined Ġby Ġhow Ċ Ġ* Ġwell Ġthe Ġvariable Ġsplits Ġthe Ġset Ġinto Ġhom ogeneous Ġsub sets Ġthat Ġhave Ċ Ġ* Ġthe Ġsame Ġvalue Ġof Ġthe Ġtarget Ġvariable . ĠDifferent Ġalgorithms Ġuse Ġdifferent Ċ Ġ* Ġform ul ae Ġfor Ġmeas uring Ġ" best ". ĠUsed Ġby Ġthe ĠC ART Ġalgorithm , ĠG ini Ġimp urity Ċ Ġ* Ġis Ġa Ġmeasure Ġof Ġhow Ġoften Ġa Ġrandomly Ġchosen Ġelement Ġfrom Ġthe Ġset Ġwould Ċ Ġ* Ġbe Ġincorrectly Ġlabeled Ġif Ġit Ġwere Ġrandomly Ġlabeled Ġaccording Ġto Ġthe Ċ Ġ* Ġdistribution Ġof Ġlabels Ġin Ġthe Ġsubset . ĠG ini Ġimp urity Ġcan Ġbe Ġcomputed Ġby Ċ Ġ* Ġsum ming Ġthe Ġprobability Ġof Ġeach Ġitem Ġbeing Ġchosen Ġtimes Ġthe Ġprobability Ċ Ġ* Ġof Ġa Ġmistake Ġin Ġc ateg oriz ing Ġthat Ġitem . ĠIt Ġreaches Ġits Ġminimum Ġ( zero ) Ġwhen Ċ Ġ* Ġall Ġcases Ġin Ġthe Ġnode Ġfall Ġinto Ġa Ġsingle Ġtarget Ġcategory . ĠInformation Ġgain Ċ Ġ* Ġis Ġanother Ġpopular Ġmeasure , Ġused Ġby Ġthe ĠID 3 , ĠC 4 . 5 Ġand ĠC 5 . 0 Ġalgorithms . Ċ Ġ* ĠInformation Ġgain Ġis Ġbased Ġon Ġthe Ġconcept Ġof Ġentropy Ġused Ġin Ġinformation Ċ Ġ* Ġtheory . ĠFor Ġcategorical Ġvariables Ġwith Ġdifferent Ġnumber Ġof Ġlevels , Ġhowever , Ċ Ġ* Ġinformation Ġgain Ġare Ġbi ased Ġin Ġfavor Ġof Ġthose Ġattributes Ġwith Ġmore Ġlevels . Ċ Ġ* ĠInstead , Ġone Ġmay Ġemploy Ġthe Ġinformation Ġgain Ġratio , Ġwhich Ġsolves Ġthe Ġdraw back Ċ Ġ* Ġof Ġinformation Ġgain . Ċ Ġ* Ċ Ġ* ĠClassification Ġand ĠRegression ĠTree Ġtechniques Ġhave Ġa Ġnumber Ġof Ġadv antages Ċ Ġ* Ġover Ġmany Ġof Ġthose Ġalternative Ġtechniques . Ċ Ġ* Ġ Ġ- Ġ''' Simple Ġto Ġunderstand Ġand Ġinterpret : ''' Ċ Ġ* ĠIn Ġmost Ġcases , Ġthe Ġinterpretation Ġof Ġresults Ġsummar ized Ġin Ġa Ġtree Ġis Ċ Ġ* Ġvery Ġsimple . ĠThis Ġsimplicity Ġis Ġuseful Ġnot Ġonly Ġfor Ġpurposes Ġof Ġrapid Ċ Ġ* Ġclassification Ġof Ġnew Ġobservations , Ġbut Ġcan Ġalso Ġoften Ġyield Ġa Ġmuch Ġsimpler Ċ Ġ* Ġ" model " Ġfor Ġexplaining Ġwhy Ġobservations Ġare Ġclass ified Ġor Ġpredicted Ġin Ġa Ċ Ġ* Ġparticular Ġmanner . Ċ Ġ* Ġ Ġ- Ġ''' Ab le Ġto Ġhandle Ġboth Ġnumerical Ġand Ġcategorical Ġdata : ''' Ċ Ġ* ĠOther Ġtechniques Ġare Ġusually Ġspecialized Ġin Ġanaly zing Ġdatasets Ġthat Ċ Ġ* Ġhave Ġonly Ġone Ġtype Ġof Ġvariable . Ċ Ġ* Ġ Ġ- Ġ''' Non parame tric Ġand Ġnonlinear : ''' Ċ Ġ* ĠThe Ġfinal Ġresults Ġof Ġusing Ġtree Ġmethods Ġfor Ġclassification Ġor Ġregression Ċ Ġ* Ġcan Ġbe Ġsummar ized Ġin Ġa Ġseries Ġof Ġ( usually Ġfew ) Ġlogical Ġif - then Ġconditions Ċ Ġ* Ġ( tree Ġnodes ). ĠTherefore , Ġthere Ġis Ġno Ġimplicit Ġassumption Ġthat Ġthe Ġunderlying Ċ Ġ* Ġrelationships Ġbetween Ġthe Ġpredictor Ġvariables Ġand Ġthe Ġdependent Ġvariable Ċ Ġ* Ġare Ġlinear , Ġfollow Ġsome Ġspecific Ġnon - linear Ġlink Ġfunction , Ġor Ġthat Ġthey Ċ Ġ* Ġare Ġeven Ġmon otonic Ġin Ġnature . ĠThus , Ġtree Ġmethods Ġare Ġparticularly Ġwell Ċ Ġ* Ġsuit ed Ġfor Ġdata Ġmining Ġtasks , Ġwhere Ġthere Ġis Ġoften Ġlittle Ġa Ġprior i Ċ Ġ* Ġknowledge Ġnor Ġany Ġco herent Ġset Ġof Ġthe ories Ġor Ġpredictions Ġregarding Ġwhich Ċ Ġ* Ġvariables Ġare Ġrelated Ġand Ġhow . ĠIn Ġthose Ġtypes Ġof Ġdata Ġanalytics , Ġtree Ċ Ġ* Ġmethods Ġcan Ġoften Ġreveal Ġsimple Ġrelationships Ġbetween Ġjust Ġa Ġfew Ġvariables Ċ Ġ* Ġthat Ġcould Ġhave Ġeasily Ġgone Ġun not iced Ġusing Ġother Ġan alytic Ġtechniques . Ċ Ġ* Ċ Ġ* ĠOne Ġmajor Ġproblem Ġwith Ġclassification Ġand Ġregression Ġtrees Ġis Ġtheir Ġhigh Ċ Ġ* Ġvariance . ĠO ft en Ġa Ġsmall Ġchange Ġin Ġthe Ġdata Ġcan Ġresult Ġin Ġa Ġvery Ġdifferent Ċ Ġ* Ġseries Ġof Ġsplits , Ġmaking Ġinterpretation Ġsomewhat Ġpre car ious . ĠBes ides , Ċ Ġ* Ġdecision - tree Ġlearn ers Ġcan Ġcreate Ġover - complex Ġtrees Ġthat Ġcause Ġover - fitting . Ċ Ġ* ĠMe chan isms Ġsuch Ġas Ġpr uning Ġare Ġnecessary Ġto Ġavoid Ġthis Ġproblem . Ċ Ġ* ĠAnother Ġlimitation Ġof Ġtrees Ġis Ġthe Ġlack Ġof Ġsmooth ness Ġof Ġthe Ġprediction Ċ Ġ* Ġsurface . Ċ Ġ* Ċ Ġ* ĠSome Ġtechniques Ġsuch Ġas Ġbag ging , Ġboost ing , Ġand Ġrandom Ġforest Ġuse Ġmore Ġthan Ċ Ġ* Ġone Ġdecision Ġtree Ġfor Ġtheir Ġanalysis . Ċ Ġ* Ċ Ġ* Ġ@ param Ġformula Ġa Ġsymbolic Ġdescription Ġof Ġthe Ġmodel Ġto Ġbe Ġfit ted . Ċ Ġ* Ġ@ param Ġdata Ġthe Ġdata Ġframe Ġof Ġthe Ġex plan atory Ġand Ġresponse Ġvariables . Ċ Ġ* Ġ@ param Ġmax Depth Ġthe Ġmaximum Ġdepth Ġof Ġthe Ġtree . Ċ Ġ* Ġ@ param Ġmax Nodes Ġthe Ġmaximum Ġnumber Ġof Ġleaf Ġnodes Ġin Ġthe Ġtree . Ċ Ġ* Ġ@ param Ġnode Size Ġthe Ġminimum Ġsize Ġof Ġleaf Ġnodes . Ċ Ġ* Ġ@ param Ġsplit Rule Ġthe Ġsplitting Ġrule . Ċ Ġ* Ġ@ return ĠDecision Ġtree Ġmodel . Ċ Ġ*/ Ċ fun Ġcart ( formula : ĠFormula , Ġdata : ĠDataFrame , Ġsplit Rule : ĠSplit Rule Ġ= ĠSplit Rule . GIN I , ĊĠĠĠĠĠĠĠĠ Ġmax Depth : ĠInt Ġ= Ġ 2 0 , Ġmax Nodes : ĠInt Ġ= Ġ 0 , Ġnode Size : ĠInt Ġ= Ġ 5 ): ĠDecision Tree Ġ{ ĊĠĠĠ Ġreturn ĠDecision Tree . fit ( formula , Ġdata , Ġsplit Rule , Ġmax Depth , Ġif Ġ( max Nodes Ġ> Ġ 0 ) Ġmax Nodes Ġelse Ġdata . size () Ġ/ Ġnode Size , Ġnode Size ) Ċ } Ċ Ċ /** Ċ Ġ* ĠRandom Ġforest Ġfor Ġclassification . ĠRandom Ġforest Ġis Ġan Ġensemble Ġclassifier Ċ Ġ* Ġthat Ġconsists Ġof Ġmany Ġdecision Ġtrees Ġand Ġoutputs Ġthe Ġmajority Ġvote Ġof Ċ Ġ* Ġindividual Ġtrees . ĠThe Ġmethod Ġcombin es Ġbag ging Ġidea Ġand Ġthe Ġrandom Ċ Ġ* Ġselection Ġof Ġfeatures . Ċ Ġ* Ċ Ġ* ĠEach Ġtree Ġis Ġconstructed Ġusing Ġthe Ġfollowing Ġalgorithm : Ċ Ġ* Ċ Ġ* ĠĠ 1 . ĠIf Ġthe Ġnumber Ġof Ġcases Ġin Ġthe Ġtraining Ġset Ġis ĠN , Ġrandomly Ġsample ĠN Ġcases Ċ Ġ* Ġwith Ġreplacement Ġfrom Ġthe Ġoriginal Ġdata . ĠThis Ġsample Ġwill Ċ Ġ* Ġbe Ġthe Ġtraining Ġset Ġfor Ġgrowing Ġthe Ġtree . Ċ Ġ* ĠĠ 2 . ĠIf Ġthere Ġare ĠM Ġinput Ġvariables , Ġa Ġnumber Ġm Ġ& lt ;& lt ; ĠM Ġis Ġspecified Ġsuch Ċ Ġ* Ġthat Ġat Ġeach Ġnode , Ġm Ġvariables Ġare Ġselected Ġat Ġrandom Ġout Ġof Ġthe ĠM Ġand Ċ Ġ* Ġthe Ġbest Ġsplit Ġon Ġthese Ġm Ġis Ġused Ġto Ġsplit Ġthe Ġnode . ĠThe Ġvalue Ġof Ġm Ġis Ċ Ġ* Ġheld Ġconstant Ġduring Ġthe Ġforest Ġgrowing . Ċ Ġ* ĠĠ 3 . ĠEach Ġtree Ġis Ġg rown Ġto Ġthe Ġlargest Ġextent Ġpossible . ĠThere Ġis Ġno Ġpr uning . Ċ Ġ* Ċ Ġ* ĠThe Ġadv antages Ġof Ġrandom Ġforest Ġare : Ċ Ġ* Ċ Ġ* Ġ Ġ- ĠFor Ġmany Ġdata Ġsets , Ġit Ġproduces Ġa Ġhighly Ġaccurate Ġclassifier . Ċ Ġ* Ġ Ġ- ĠIt Ġruns Ġefficiently Ġon Ġlarge Ġdata Ġsets . Ċ Ġ* Ġ Ġ- ĠIt Ġcan Ġhandle Ġthousands Ġof Ġinput Ġvariables Ġwithout Ġvariable Ġdeletion . Ċ Ġ* Ġ Ġ- ĠIt Ġgives Ġestimates Ġof Ġwhat Ġvariables Ġare Ġimportant Ġin Ġthe Ġclassification . Ċ Ġ* Ġ Ġ- ĠIt Ġgenerates Ġan Ġinternal Ġun bi ased Ġestimate Ġof Ġthe Ġgeneral ization Ġerror Ċ Ġ* Ġas Ġthe Ġforest Ġbuilding Ġprog resses . Ċ Ġ* Ġ Ġ- ĠIt Ġhas Ġan Ġeffective Ġmethod Ġfor Ġestim ating Ġmissing Ġdata Ġand Ġmaintains Ċ Ġ* Ġaccuracy Ġwhen Ġa Ġlarge Ġproportion Ġof Ġthe Ġdata Ġare Ġmissing . Ċ Ġ* Ċ Ġ* ĠThe Ġdis adv antages Ġare Ċ Ġ* Ċ Ġ* Ġ Ġ- ĠRandom Ġfore sts Ġare Ġpr one Ġto Ġover - fitting Ġfor Ġsome Ġdatasets . ĠThis Ġis Ċ Ġ* Ġeven Ġmore Ġpr ono unced Ġon Ġno isy Ġdata . Ċ Ġ* Ġ Ġ- ĠFor Ġdata Ġincluding Ġcategorical Ġvariables Ġwith Ġdifferent Ġnumber Ġof Ċ Ġ* Ġlevels , Ġrandom Ġfore sts Ġare Ġbi ased Ġin Ġfavor Ġof Ġthose Ġattributes Ġwith Ġmore Ċ Ġ* Ġlevels . ĠTherefore , Ġthe Ġvariable Ġimportance Ġscores Ġfrom Ġrandom Ġforest Ġare Ċ Ġ* Ġnot Ġreliable Ġfor Ġthis Ġtype Ġof Ġdata . Ċ Ġ* Ċ Ġ* Ġ@ param Ġformula Ġa Ġsymbolic Ġdescription Ġof Ġthe Ġmodel Ġto Ġbe Ġfit ted . Ċ Ġ* Ġ@ param Ġdata Ġthe Ġdata Ġframe Ġof Ġthe Ġex plan atory Ġand Ġresponse Ġvariables . Ċ Ġ* Ġ@ param Ġn trees Ġthe Ġnumber Ġof Ġtrees . Ċ Ġ* Ġ@ param Ġm try Ġthe Ġnumber Ġof Ġrandom Ġselected Ġfeatures Ġto Ġbe Ġused Ġto Ġdetermine Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠ Ġthe Ġdecision Ġat Ġa Ġnode Ġof Ġthe Ġtree . Ġfloor ( sqrt ( dim )) Ġseems Ġto Ġgive Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠ Ġgenerally Ġgood Ġperformance , Ġwhere Ġdim Ġis Ġthe Ġnumber Ġof Ġvariables . Ċ Ġ* Ġ@ param Ġmax Depth Ġthe Ġmaximum Ġdepth Ġof Ġthe Ġtree . Ċ Ġ* Ġ@ param Ġmax Nodes Ġthe Ġmaximum Ġnumber Ġof Ġleaf Ġnodes Ġin Ġthe Ġtree . Ċ Ġ* Ġ@ param Ġnode Size Ġthe Ġminimum Ġsize Ġof Ġleaf Ġnodes . Ċ Ġ* Ġ@ param Ġsub sample Ġthe Ġsampling Ġrate Ġfor Ġtraining Ġtree . Ġ 1 . 0 Ġmeans Ġsampling Ġwith Ġreplacement . Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ< Ġ 1 . 0 Ġmeans Ġsampling Ġwithout Ġreplacement . Ċ Ġ* Ġ@ param Ġsplit Rule ĠDecision Ġtree Ġnode Ġsplit Ġrule . Ċ Ġ* Ġ@ return ĠRandom Ġforest Ġclassification Ġmodel . Ċ Ġ*/ Ċ fun Ġrandom Forest ( formula : ĠFormula , Ġdata : ĠDataFrame , Ġn trees : ĠInt Ġ= Ġ 5 0 0 , Ġm try : ĠInt Ġ= Ġ 0 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsplit Rule : ĠSplit Rule Ġ= ĠSplit Rule . GIN I , Ġmax Depth : ĠInt Ġ= Ġ 2 0 , Ġmax Nodes : ĠInt Ġ= Ġ 5 0 0 , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnode Size : ĠInt Ġ= Ġ 1 , Ġsub sample : ĠDouble Ġ= Ġ 1 . 0 , Ġclass Weight : ĠInt Array ? Ġ= Ġnull , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġseeds : ĠLong Stream ? Ġ= Ġnull ): ĠRandom Forest Ġ{ ĊĠĠĠ Ġreturn ĠRandom Forest . fit ( formula , Ġdata , Ġn trees , Ġm try , Ġsplit Rule , Ġmax Depth , Ġmax Nodes , Ġnode Size , Ġsub sample , Ġclass Weight , Ġseeds ) Ċ } Ċ Ċ /** Ċ Ġ* ĠGradient Ġboost ed Ġclassification Ġtrees . Ċ Ġ* Ċ Ġ* ĠGeneric Ġgradient Ġboost ing Ġat Ġthe Ġt - th Ġstep Ġwould Ġfit Ġa Ġregression Ġtree Ġto Ċ Ġ* Ġpseudo - residual s . ĠLet ĠJ Ġbe Ġthe Ġnumber Ġof Ġits Ġleaves . ĠThe Ġtree Ġpartitions Ċ Ġ* Ġthe Ġinput Ġspace Ġinto ĠJ Ġdis joint Ġregions Ġand Ġpredict s Ġa Ġconstant Ġvalue Ġin Ċ Ġ* Ġeach Ġregion . ĠThe Ġparameter ĠJ Ġcontrols Ġthe Ġmaximum Ġallowed Ċ Ġ* Ġlevel Ġof Ġinteraction Ġbetween Ġvariables Ġin Ġthe Ġmodel . ĠWith ĠJ Ġ= Ġ 2 Ġ( decision Ċ Ġ* Ġst ump s ), Ġno Ġinteraction Ġbetween Ġvariables Ġis Ġallowed . ĠWith ĠJ Ġ= Ġ 3 Ġthe Ġmodel Ċ Ġ* Ġmay Ġinclude Ġeffects Ġof Ġthe Ġinteraction Ġbetween Ġup Ġto Ġtwo Ġvariables , Ġand Ċ Ġ* Ġso Ġon . ĠH ast ie Ġet Ġal . Ġcomment Ġthat Ġtypically Ġ 4 Ġ& le ; ĠJ Ġ& le ; Ġ 8 Ġwork Ġwell Ċ Ġ* Ġfor Ġboost ing Ġand Ġresults Ġare Ġfairly Ġins ensitive Ġto Ġthe Ġchoice Ġof Ġin Ċ Ġ* Ġthis Ġrange , ĠJ Ġ= Ġ 2 Ġis Ġins ufficient Ġfor Ġmany Ġapplications , Ġand ĠJ Ġ& gt ; Ġ 1 0 Ġis Ċ Ġ* Ġunlikely Ġto Ġbe Ġrequired . Ċ Ġ* Ċ Ġ* ĠFit ting Ġthe Ġtraining Ġset Ġtoo Ġclosely Ġcan Ġlead Ġto Ġde grad ation Ġof Ġthe Ġmodel 's Ċ Ġ* Ġgeneral ization Ġability . ĠSe veral Ġso - called Ġregular ization Ġtechniques Ġreduce Ċ Ġ* Ġthis Ġover - fitting Ġeffect Ġby Ġconstr aining Ġthe Ġfitting Ġprocedure . Ċ Ġ* ĠOne Ġnatural Ġregular ization Ġparameter Ġis Ġthe Ġnumber Ġof Ġgradient Ġboost ing Ċ Ġ* Ġiterations ĠT Ġ( i . e . Ġthe Ġnumber Ġof Ġtrees Ġin Ġthe Ġmodel Ġwhen Ġthe Ġbase Ġle arner Ċ Ġ* Ġis Ġa Ġdecision Ġtree ). ĠIn creasing ĠT Ġreduces Ġthe Ġerror Ġon Ġtraining Ġset , Ċ Ġ* Ġbut Ġsetting Ġit Ġtoo Ġhigh Ġmay Ġlead Ġto Ġover - fitting . ĠAn Ġoptimal Ġvalue Ġof ĠT Ċ Ġ* Ġis Ġoften Ġselected Ġby Ġmonitoring Ġprediction Ġerror Ġon Ġa Ġseparate Ġvalidation Ċ Ġ* Ġdata Ġset . Ċ Ġ* Ċ Ġ* ĠAnother Ġregular ization Ġapproach Ġis Ġthe Ġshrink age Ġwhich Ġtimes Ġa Ġparameter Ċ Ġ* Ġ& eta ; Ġ( called Ġthe Ġ" learning Ġrate ") Ġto Ġupdate Ġterm . Ċ Ġ* ĠEmp ir ically Ġit Ġhas Ġbeen Ġfound Ġthat Ġusing Ġsmall Ġlearning Ġrates Ġ( such Ġas Ċ Ġ* Ġ& eta ; Ġ& lt ; Ġ 0 . 1 ) Ġyields Ġd ram atic Ġimprovements Ġin Ġmodel 's Ġgeneral ization Ġability Ċ Ġ* Ġover Ġgradient Ġboost ing Ġwithout Ġshrink ing Ġ(& eta ; Ġ= Ġ 1 ). ĠHowever , Ġit Ġcomes Ġat Ċ Ġ* Ġthe Ġprice Ġof Ġincreasing Ġcomputational Ġtime Ġboth Ġduring Ġtraining Ġand Ċ Ġ* Ġprediction : Ġlower Ġlearning Ġrate Ġrequires Ġmore Ġiterations . Ċ Ġ* Ċ Ġ* ĠSo on Ġafter Ġthe Ġintroduction Ġof Ġgradient Ġboost ing ĠF ried man Ġproposed Ġa Ċ Ġ* Ġminor Ġmodification Ġto Ġthe Ġalgorithm , Ġmot iv ated Ġby ĠBre im an 's Ġbag ging Ġmethod . Ċ Ġ* ĠSpecific ally , Ġhe Ġproposed Ġthat Ġat Ġeach Ġiteration Ġof Ġthe Ġalgorithm , Ġa Ġbase Ċ Ġ* Ġle arner Ġshould Ġbe Ġfit Ġon Ġa Ġsub sample Ġof Ġthe Ġtraining Ġset Ġdrawn Ġat Ġrandom Ċ Ġ* Ġwithout Ġreplacement . ĠF ried man Ġobserved Ġa Ġsubstantial Ġimprovement Ġin Ċ Ġ* Ġgradient Ġboost ing 's Ġaccuracy Ġwith Ġthis Ġmodification . Ċ Ġ* Ċ Ġ* ĠSub sample Ġsize Ġis Ġsome Ġconstant Ġfraction Ġf Ġof Ġthe Ġsize Ġof Ġthe Ġtraining Ġset . Ċ Ġ* ĠWhen Ġf Ġ= Ġ 1 , Ġthe Ġalgorithm Ġis Ġdeterministic Ġand Ġidentical Ġto Ġthe Ġone Ċ Ġ* Ġdescribed Ġabove . ĠSmall er Ġvalues Ġof Ġf Ġintroduce Ġrandom ness Ġinto Ġthe Ċ Ġ* Ġalgorithm Ġand Ġhelp Ġprevent Ġover - fitting , Ġact ing Ġas Ġa Ġkind Ġof Ġregular ization . Ċ Ġ* ĠThe Ġalgorithm Ġalso Ġbecomes Ġfaster , Ġbecause Ġregression Ġtrees Ġhave Ġto Ġbe Ġfit Ċ Ġ* Ġto Ġsmaller Ġdatasets Ġat Ġeach Ġiteration . ĠTypically , Ġf Ġis Ġset Ġto Ġ 0 . 5 , Ġmeaning Ċ Ġ* Ġthat Ġone Ġhalf Ġof Ġthe Ġtraining Ġset Ġis Ġused Ġto Ġbuild Ġeach Ġbase Ġle arner . Ċ Ġ* Ċ Ġ* ĠAlso , Ġlike Ġin Ġbag ging , Ġsub - sampling Ġallows Ġone Ġto Ġdefine Ġan Ġout - of - bag Ċ Ġ* Ġestimate Ġof Ġthe Ġprediction Ġperformance Ġimprovement Ġby Ġevaluating Ġpredictions Ċ Ġ* Ġon Ġthose Ġobservations Ġwhich Ġwere Ġnot Ġused Ġin Ġthe Ġbuilding Ġof Ġthe Ġnext Ċ Ġ* Ġbase Ġle arner . ĠOut - of - bag Ġestimates Ġhelp Ġavoid Ġthe Ġneed Ġfor Ġan Ġindependent Ċ Ġ* Ġvalidation Ġdataset , Ġbut Ġoften Ġunder estimate Ġactual Ġperformance Ġimprovement Ċ Ġ* Ġand Ġthe Ġoptimal Ġnumber Ġof Ġiterations . Ċ Ġ* Ċ Ġ* ĠGradient Ġtree Ġboost ing Ġimplementations Ġoften Ġalso Ġuse Ġregular ization Ġby Ċ Ġ* Ġlimiting Ġthe Ġminimum Ġnumber Ġof Ġobservations Ġin Ġtrees ' Ġterminal Ġnodes . Ċ Ġ* ĠIt 's Ġused Ġin Ġthe Ġtree Ġbuilding Ġprocess Ġby Ġignoring Ġany Ġsplits Ġthat Ġlead Ċ Ġ* Ġto Ġnodes Ġcontaining Ġfewer Ġthan Ġthis Ġnumber Ġof Ġtraining Ġset Ġinstances . Ċ Ġ* ĠImp osing Ġthis Ġlimit Ġhelps Ġto Ġreduce Ġvariance Ġin Ġpredictions Ġat Ġleaves . Ċ Ġ* Ċ Ġ* Ġ=== = References : ==== Ċ Ġ* Ġ Ġ- ĠJ . ĠH . ĠF ried man . ĠG reedy ĠFunction ĠAppro x imation : ĠA ĠGradient ĠBoost ing ĠMachine , Ġ 1 9 9 9 . Ċ Ġ* Ġ Ġ- ĠJ . ĠH . ĠF ried man . ĠSto chastic ĠGradient ĠBoost ing , Ġ 1 9 9 9 . Ċ Ġ* Ċ Ġ* Ġ@ param Ġformula Ġa Ġsymbolic Ġdescription Ġof Ġthe Ġmodel Ġto Ġbe Ġfit ted . Ċ Ġ* Ġ@ param Ġdata Ġthe Ġdata Ġframe Ġof Ġthe Ġex plan atory Ġand Ġresponse Ġvariables . Ċ Ġ* Ġ@ param Ġn trees Ġthe Ġnumber Ġof Ġiterations Ġ( trees ). Ċ Ġ* Ġ@ param Ġmax Depth Ġthe Ġmaximum Ġdepth Ġof Ġthe Ġtree . Ċ Ġ* Ġ@ param Ġmax Nodes Ġthe Ġmaximum Ġnumber Ġof Ġleaf Ġnodes Ġin Ġthe Ġtree . Ċ Ġ* Ġ@ param Ġnode Size Ġthe Ġminimum Ġsize Ġof Ġleaf Ġnodes . Ċ Ġ* Ġ@ param Ġshrink age Ġthe Ġshrink age Ġparameter Ġin Ġ( 0 , Ġ 1 ] Ġcontrols Ġthe Ġlearning Ġrate Ġof Ġprocedure . Ċ Ġ* Ġ@ param Ġsub sample Ġthe Ġsampling Ġfraction Ġfor Ġst och astic Ġtree Ġboost ing . Ċ Ġ* Ċ Ġ* Ġ@ return ĠGradient Ġboost ed Ġtrees . Ċ Ġ*/ Ċ fun Ġg bm ( formula : ĠFormula , Ġdata : ĠDataFrame , Ġn trees : ĠInt Ġ= Ġ 5 0 0 , Ġmax Depth : ĠInt Ġ= Ġ 2 0 , Ġmax Nodes : ĠInt Ġ= Ġ 6 , ĊĠĠĠĠĠĠĠ Ġnode Size : ĠInt Ġ= Ġ 5 , Ġshrink age : ĠDouble Ġ= Ġ 0 . 0 5 , Ġsub sample : ĠDouble Ġ= Ġ 0 . 7 ): ĠGradient Tree Boost Ġ{ ĊĠĠĠ Ġreturn ĠGradient Tree Boost . fit ( formula , Ġdata , Ġn trees , Ġmax Depth , Ġmax Nodes , Ġnode Size , Ġshrink age , Ġsub sample ) Ċ } Ċ Ċ /** Ċ Ġ* ĠAda Boost Ġ( Adaptive ĠBoost ing ) Ġclassifier Ġwith Ġdecision Ġtrees . ĠIn Ġprinciple , Ċ Ġ* ĠAda Boost Ġis Ġa Ġmeta - algorithm , Ġand Ġcan Ġbe Ġused Ġin Ġconjunction Ġwith Ġmany Ġother Ċ Ġ* Ġlearning Ġalgorithms Ġto Ġimprove Ġtheir Ġperformance . ĠIn Ġpractice , ĠAda Boost Ġwith Ċ Ġ* Ġdecision Ġtrees Ġis Ġprobably Ġthe Ġmost Ġpopular Ġcombination . ĠAda Boost Ġis Ġadaptive Ċ Ġ* Ġin Ġthe Ġsense Ġthat Ġsubsequent Ġclassifiers Ġbuilt Ġare Ġtweak ed Ġin Ġfavor Ġof Ġthose Ċ Ġ* Ġinstances Ġmis class ified Ġby Ġprevious Ġclassifiers . ĠAda Boost Ġis Ġsensitive Ġto Ċ Ġ* Ġno isy Ġdata Ġand Ġout liers . ĠHowever Ġin Ġsome Ġproblems Ġit Ġcan Ġbe Ġless Ġsus cept ible Ċ Ġ* Ġto Ġthe Ġover - fitting Ġproblem Ġthan Ġmost Ġlearning Ġalgorithms . Ċ Ġ* Ċ Ġ* ĠAda Boost Ġcalls Ġa Ġweak Ġclassifier Ġrepeatedly Ġin Ġa Ġseries Ġof Ġrounds Ġfrom Ċ Ġ* Ġtotal ĠT Ġclassifiers . ĠFor Ġeach Ġcall Ġa Ġdistribution Ġof Ġweights Ġis Ġupdated Ċ Ġ* Ġthat Ġindicates Ġthe Ġimportance Ġof Ġexamples Ġin Ġthe Ġdata Ġset Ġfor Ġthe Ċ Ġ* Ġclassification . ĠOn Ġeach Ġround , Ġthe Ġweights Ġof Ġeach Ġincorrectly Ġclass ified Ċ Ġ* Ġexample Ġare Ġincreased Ġ( or Ġaltern atively , Ġthe Ġweights Ġof Ġeach Ġcorrectly Ċ Ġ* Ġclass ified Ġexample Ġare Ġdecrease d ), Ġso Ġthat Ġthe Ġnew Ġclassifier Ġfoc uses Ġmore Ċ Ġ* Ġon Ġthose Ġexamples . Ċ Ġ* Ċ Ġ* ĠThe Ġbasic ĠAda Boost Ġalgorithm Ġis Ġonly Ġfor Ġbinary Ġclassification Ġproblem . Ċ Ġ* ĠFor Ġmulti - class Ġclassification , Ġa Ġcommon Ġapproach Ġis Ġreducing Ġthe Ċ Ġ* Ġmulti - class Ġclassification Ġproblem Ġto Ġmultiple Ġtwo - class Ġproblems . Ċ Ġ* ĠThis Ġimplementation Ġis Ġa Ġmulti - class ĠAda Boost Ġwithout Ġsuch Ġreduction s . Ċ Ġ* Ċ Ġ* Ġ=== = References : ==== Ċ Ġ* Ġ Ġ- ĠYo av ĠFre und , ĠRobert ĠE . ĠSch ap ire . ĠA ĠDecision - The ore tic ĠGeneral ization Ġof Ġon - Line ĠLearning Ġand Ġan ĠApplication Ġto ĠBoost ing , Ġ 1 9 9 5 . Ċ Ġ* Ġ Ġ- ĠJ i ĠZ hu , ĠH ui ĠZ hou , ĠS ah aron ĠRos set Ġand ĠT rev or ĠH ast ie . ĠMulti - class ĠAd ab oost , Ġ 2 0 0 9 . Ċ Ġ* Ċ Ġ* Ġ@ param Ġformula Ġa Ġsymbolic Ġdescription Ġof Ġthe Ġmodel Ġto Ġbe Ġfit ted . Ċ Ġ* Ġ@ param Ġdata Ġthe Ġdata Ġframe Ġof Ġthe Ġex plan atory Ġand Ġresponse Ġvariables . Ċ Ġ* Ġ@ param Ġn trees Ġthe Ġnumber Ġof Ġtrees . Ċ Ġ* Ġ@ param Ġmax Depth Ġthe Ġmaximum Ġdepth Ġof Ġthe Ġtree . Ċ Ġ* Ġ@ param Ġmax Nodes Ġthe Ġmaximum Ġnumber Ġof Ġleaf Ġnodes Ġin Ġthe Ġtree . Ċ Ġ* Ġ@ param Ġnode Size Ġthe Ġminimum Ġsize Ġof Ġleaf Ġnodes . Ċ Ġ* Ċ Ġ* Ġ@ return ĠAda Boost Ġmodel . Ċ Ġ*/ Ċ fun Ġad ab oost ( formula : ĠFormula , Ġdata : ĠDataFrame , Ġn trees : ĠInt Ġ= Ġ 5 0 0 , Ġmax Depth : ĠInt Ġ= Ġ 2 0 , ĊĠĠĠĠĠĠĠĠĠĠĠĠ Ġmax Nodes : ĠInt Ġ= Ġ 6 , Ġnode Size : ĠInt Ġ= Ġ 1 ): ĠAda Boost Ġ{ ĊĠĠĠ Ġreturn ĠAda Boost . fit ( formula , Ġdata , Ġn trees , Ġmax Depth , Ġmax Nodes , Ġnode Size ) Ċ } Ċ Ċ /** Ċ Ġ* ĠFish er 's Ġlinear Ġdis crimin ant . ĠFish er Ġdefined Ġthe Ġseparation Ġbetween Ġtwo Ċ Ġ* Ġdistributions Ġto Ġbe Ġthe Ġratio Ġof Ġthe Ġvariance Ġbetween Ġthe Ġclasses Ġto Ċ Ġ* Ġthe Ġvariance Ġwithin Ġthe Ġclasses , Ġwhich Ġis , Ġin Ġsome Ġsense , Ġa Ġmeasure Ċ Ġ* Ġof Ġthe Ġsignal - to - noise Ġratio Ġfor Ġthe Ġclass Ġlabel ing . ĠF LD Ġfinds Ġa Ġlinear Ċ Ġ* Ġcombination Ġof Ġfeatures Ġwhich Ġmaxim izes Ġthe Ġseparation Ġafter Ġthe Ġprojection . Ċ Ġ* ĠThe Ġresulting Ġcombination Ġmay Ġbe Ġused Ġfor Ġdimension ality Ġreduction Ċ Ġ* Ġbefore Ġlater Ġclassification . Ċ Ġ* Ċ Ġ* ĠThe Ġterms ĠFish er 's Ġlinear Ġdis crimin ant Ġand ĠL DA Ġare Ġoften Ġused Ċ Ġ* Ġinter change ably , Ġalthough ĠF LD Ġactually Ġdescribes Ġa Ġslightly Ġdifferent Ċ Ġ* Ġdis crimin ant , Ġwhich Ġdoes Ġnot Ġmake Ġsome Ġof Ġthe Ġassumptions Ġof ĠL DA Ġsuch Ċ Ġ* Ġas Ġnormally Ġdistributed Ġclasses Ġor Ġequal Ġclass Ġco var ian ces . Ċ Ġ* ĠWhen Ġthe Ġassumptions Ġof ĠL DA Ġare Ġsatisfied , ĠF LD Ġis Ġequivalent Ġto ĠL DA . Ċ Ġ* Ċ Ġ* ĠF LD Ġis Ġalso Ġclosely Ġrelated Ġto Ġprincipal Ġcomponent Ġanalysis Ġ( PCA ), Ġwhich Ġalso Ċ Ġ* Ġlooks Ġfor Ġlinear Ġcombinations Ġof Ġvariables Ġwhich Ġbest Ġexplain Ġthe Ġdata . Ċ Ġ* ĠAs Ġa Ġsuper vised Ġmethod , ĠF LD Ġexplicitly Ġattempts Ġto Ġmodel Ġthe Ċ Ġ* Ġdifference Ġbetween Ġthe Ġclasses Ġof Ġdata . ĠOn Ġthe Ġother Ġhand , ĠPCA Ġis Ġa Ċ Ġ* Ġun supervised Ġmethod Ġand Ġdoes Ġnot Ġtake Ġinto Ġaccount Ġany Ġdifference Ġin Ġclass . Ċ Ġ* Ċ Ġ* ĠOne Ġcomp lication Ġin Ġapplying ĠF LD Ġ( and ĠL DA ) Ġto Ġreal Ġdata Ċ Ġ* Ġoccurs Ġwhen Ġthe Ġnumber Ġof Ġvariables / features Ġdoes Ġnot Ġexceed Ċ Ġ* Ġthe Ġnumber Ġof Ġsamples . ĠIn Ġthis Ġcase , Ġthe Ġcovariance Ġestimates Ġdo Ġnot Ġhave Ċ Ġ* Ġfull Ġrank , Ġand Ġso Ġcannot Ġbe Ġinverted . ĠThis Ġis Ġknown Ġas Ġsmall Ġsample Ġsize Ċ Ġ* Ġproblem . Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġtraining Ġinstances . Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ġin Ġ[ 0 , Ġk ), Ġwhere Ġk Ġis Ġthe Ġnumber Ġof Ġclasses . Ċ Ġ* Ġ@ param ĠL Ġthe Ġdimension ality Ġof Ġmapped Ġspace . ĠThe Ġdefault Ġvalue Ġis Ġthe Ġnumber Ġof Ġclasses Ġ- Ġ 1 . Ċ Ġ* Ġ@ param Ġtol Ġa Ġtolerance Ġto Ġdecide Ġif Ġa Ġcovariance Ġmatrix Ġis Ġsingular ; Ġit Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠ Ġwill Ġreject Ġvariables Ġwhose Ġvariance Ġis Ġless Ġthan Ġtol < sup > 2 </ sup >. Ċ Ġ* Ċ Ġ* Ġ@ return Ġfish er Ġdis crimin ant Ġanalysis Ġmodel . Ċ Ġ*/ Ċ fun Ġfish er ( x : ĠArray < Double Array >, Ġy : ĠInt Array , ĠL : ĠInt Ġ= Ġ- 1 , Ġtol : ĠDouble Ġ= Ġ 0 . 0 0 0 1 ): ĠF LD Ġ{ ĊĠĠĠ Ġreturn ĠF LD . fit ( x , Ġy , ĠL , Ġtol ) Ċ } Ċ Ċ /** Ċ Ġ* ĠLinear Ġdis crimin ant Ġanalysis . ĠL DA Ġis Ġbased Ġon Ġthe ĠBay es Ġdecision Ġtheory Ċ Ġ* Ġand Ġassumes Ġthat Ġthe Ġconditional Ġprobability Ġdensity Ġfunctions Ġare Ġnormally Ċ Ġ* Ġdistributed . ĠL DA Ġalso Ġmakes Ġthe Ġsimpl ifying Ġhom os ced astic Ġassumption Ġ( i . e . Ċ Ġ* Ġthat Ġthe Ġclass Ġco var ian ces Ġare Ġidentical ) Ġand Ġthat Ġthe Ġco var ian ces Ġhave Ġfull Ċ Ġ* Ġrank . ĠWith Ġthese Ġassumptions , Ġthe Ġdis crimin ant Ġfunction Ġof Ġan Ġinput Ġbeing Ċ Ġ* Ġin Ġa Ġclass Ġis Ġpure ly Ġa Ġfunction Ġof Ġthis Ġlinear Ġcombination Ġof Ġindependent Ċ Ġ* Ġvariables . Ċ Ġ* Ċ Ġ* ĠL DA Ġis Ġclosely Ġrelated Ġto ĠAN O VA Ġ( analysis Ġof Ġvariance ) Ġand Ġlinear Ġregression Ċ Ġ* Ġanalysis , Ġwhich Ġalso Ġattempt Ġto Ġexpress Ġone Ġdependent Ġvariable Ġas Ġa Ċ Ġ* Ġlinear Ġcombination Ġof Ġother Ġfeatures Ġor Ġmeasurements . ĠIn Ġthe Ġother Ġtwo Ċ Ġ* Ġmethods , Ġhowever , Ġthe Ġdependent Ġvariable Ġis Ġa Ġnumerical Ġquantity , Ġwhile Ċ Ġ* Ġfor ĠL DA Ġit Ġis Ġa Ġcategorical Ġvariable Ġ( i . e . Ġthe Ġclass Ġlabel ). ĠLog istic Ċ Ġ* Ġregression Ġand Ġprob it Ġregression Ġare Ġmore Ġsimilar Ġto ĠL DA , Ġas Ġthey Ġalso Ċ Ġ* Ġexplain Ġa Ġcategorical Ġvariable . ĠThese Ġother Ġmethods Ġare Ġprefer able Ġin Ċ Ġ* Ġapplications Ġwhere Ġit Ġis Ġnot Ġreasonable Ġto Ġassume Ġthat Ġthe Ġindependent Ċ Ġ* Ġvariables Ġare Ġnormally Ġdistributed , Ġwhich Ġis Ġa Ġfundamental Ġassumption Ċ Ġ* Ġof Ġthe ĠL DA Ġmethod . Ċ Ġ* Ċ Ġ* ĠOne Ġcomp lication Ġin Ġapplying ĠL DA Ġ( and ĠFish er 's Ġdis crimin ant ) Ġto Ġreal Ġdata Ċ Ġ* Ġoccurs Ġwhen Ġthe Ġnumber Ġof Ġvariables / features Ġdoes Ġnot Ġexceed Ċ Ġ* Ġthe Ġnumber Ġof Ġsamples . ĠIn Ġthis Ġcase , Ġthe Ġcovariance Ġestimates Ġdo Ġnot Ġhave Ċ Ġ* Ġfull Ġrank , Ġand Ġso Ġcannot Ġbe Ġinverted . ĠThis Ġis Ġknown Ġas Ġsmall Ġsample Ġsize Ċ Ġ* Ġproblem . Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġtraining Ġsamples . Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ġin Ġ[ 0 , Ġk ), Ġwhere Ġk Ġis Ġthe Ġnumber Ġof Ġclasses . Ċ Ġ* Ġ@ param Ġprior i Ġthe Ġprior i Ġprobability Ġof Ġeach Ġclass . ĠIf Ġnull , Ġit Ġwill Ġbe Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġestimated Ġfrom Ġthe Ġtraining Ġdata . Ċ Ġ* Ġ@ param Ġtol Ġa Ġtolerance Ġto Ġdecide Ġif Ġa Ġcovariance Ġmatrix Ġis Ġsingular ; Ġit Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠ Ġwill Ġreject Ġvariables Ġwhose Ġvariance Ġis Ġless Ġthan Ġtol < sup > 2 </ sup >. Ċ Ġ* Ċ Ġ* Ġ@ return Ġlinear Ġdis crimin ant Ġanalysis Ġmodel . Ċ Ġ*/ Ċ fun Ġlda ( x : ĠArray < Double Array >, Ġy : ĠInt Array , Ġprior i : ĠDouble Array ? Ġ= Ġnull , Ġtol : ĠDouble Ġ= Ġ 0 . 0 0 0 1 ): ĠL DA Ġ{ ĊĠĠĠ Ġreturn ĠL DA . fit ( x , Ġy , Ġprior i , Ġtol ) Ċ } Ċ Ċ /** Ċ Ġ* ĠQu adr atic Ġdis crimin ant Ġanalysis . ĠQ DA Ġis Ġclosely Ġrelated Ġto Ġlinear Ġdis crimin ant Ċ Ġ* Ġanalysis Ġ( L DA ). ĠLike ĠL DA , ĠQ DA Ġmodels Ġthe Ġconditional Ġprobability Ġdensity Ċ Ġ* Ġfunctions Ġas Ġa ĠGaussian Ġdistribution , Ġthen Ġuses Ġthe Ġposterior Ġdistributions Ċ Ġ* Ġto Ġestimate Ġthe Ġclass Ġfor Ġa Ġgiven Ġtest Ġdata . ĠUn like ĠL DA , Ġhowever , Ċ Ġ* Ġin ĠQ DA Ġthere Ġis Ġno Ġassumption Ġthat Ġthe Ġcovariance Ġof Ġeach Ġof Ġthe Ġclasses Ċ Ġ* Ġis Ġidentical . ĠTherefore , Ġthe Ġresulting Ġsepar ating Ġsurface Ġbetween Ċ Ġ* Ġthe Ġclasses Ġis Ġquadr atic . Ċ Ġ* Ċ Ġ* ĠThe ĠGaussian Ġparameters Ġfor Ġeach Ġclass Ġcan Ġbe Ġestimated Ġfrom Ġtraining Ġdata Ċ Ġ* Ġwith Ġmaximum Ġlikelihood Ġ( ML ) Ġestimation . ĠHowever , Ġwhen Ġthe Ġnumber Ġof Ċ Ġ* Ġtraining Ġinstances Ġis Ġsmall Ġcompared Ġto Ġthe Ġdimension Ġof Ġinput Ġspace , Ċ Ġ* Ġthe ĠML Ġcovariance Ġestimation Ġcan Ġbe Ġill - posed . ĠOne Ġapproach Ġto Ġresolve Ċ Ġ* Ġthe Ġill - posed Ġestimation Ġis Ġto Ġregular ize Ġthe Ġcovariance Ġestimation . Ċ Ġ* ĠOne Ġof Ġthese Ġregular ization Ġmethods Ġis Ġ{@ link Ġr da Ġregular ized Ġdis crimin ant Ġanalysis }. Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġtraining Ġsamples . Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ġin Ġ[ 0 , Ġk ), Ġwhere Ġk Ġis Ġthe Ġnumber Ġof Ġclasses . Ċ Ġ* Ġ@ param Ġprior i Ġthe Ġprior i Ġprobability Ġof Ġeach Ġclass . ĠIf Ġnull , Ġit Ġwill Ġbe Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġestimated Ġfrom Ġthe Ġtraining Ġdata . Ċ Ġ* Ġ@ param Ġtol Ġa Ġtolerance Ġto Ġdecide Ġif Ġa Ġcovariance Ġmatrix Ġis Ġsingular ; Ġit Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠ Ġwill Ġreject Ġvariables Ġwhose Ġvariance Ġis Ġless Ġthan Ġtol < sup > 2 </ sup >. Ċ Ġ* Ċ Ġ* Ġ@ return ĠQu adr atic Ġdis crimin ant Ġanalysis Ġmodel . Ċ Ġ*/ Ċ fun Ġq da ( x : ĠArray < Double Array >, Ġy : ĠInt Array , Ġprior i : ĠDouble Array ? Ġ= Ġnull , Ġtol : ĠDouble Ġ= Ġ 0 . 0 0 0 1 ): ĠQ DA Ġ{ ĊĠĠĠ Ġreturn ĠQ DA . fit ( x , Ġy , Ġprior i , Ġtol ) Ċ } Ċ Ċ /** Ċ Ġ* ĠRegular ized Ġdis crimin ant Ġanalysis . ĠR DA Ġis Ġa Ġcomp romise Ġbetween ĠL DA Ġand ĠQ DA , Ċ Ġ* Ġwhich Ġallows Ġone Ġto Ġshrink Ġthe Ġseparate Ġco var ian ces Ġof ĠQ DA Ġtoward Ġa Ġcommon Ċ Ġ* Ġvariance Ġas Ġin ĠL DA . ĠThis Ġmethod Ġis Ġvery Ġsimilar Ġin Ġflavor Ġto Ġrid ge Ġregression . Ċ Ġ* ĠThe Ġregular ized Ġcovariance Ġmatrices Ġof Ġeach Ġclass Ġis Ċ Ġ* Ġ& Sigma ;< sub > k </ sub >(& alpha ;) Ġ= Ġ& alpha ; Ġ& Sigma ;< sub > k </ sub > Ġ+ Ġ( 1 Ġ- Ġ& alpha ;) Ġ& Sigma ;. Ċ Ġ* ĠThe Ġquadr atic Ġdis crimin ant Ġfunction Ġis Ġdefined Ġusing Ġthe Ġsh run ken Ġcovariance Ċ Ġ* Ġmatrices Ġ& Sigma ;< sub > k </ sub >(& alpha ; ). ĠThe Ġparameter Ġ& alpha ; Ġin Ġ`[ 0 , Ġ 1 ]` Ċ Ġ* Ġcontrols Ġthe Ġcomplexity Ġof Ġthe Ġmodel . ĠWhen Ġ& alpha ; Ġis Ġone , ĠR DA Ġbecomes ĠQ DA . Ċ Ġ* ĠWhile Ġ& alpha ; Ġis Ġzero , ĠR DA Ġis Ġequivalent Ġto ĠL DA . ĠTherefore , Ġthe Ċ Ġ* Ġregular ization Ġfactor Ġ& alpha ; Ġallows Ġa Ġcontinu um Ġof Ġmodels Ġbetween ĠL DA Ġand ĠQ DA . Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġtraining Ġsamples . Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ġin Ġ`[ 0 , Ġk )`, Ġwhere Ġk Ġis Ġthe Ġnumber Ġof Ġclasses . Ċ Ġ* Ġ@ param Ġalpha Ġregular ization Ġfactor Ġin Ġ`[ 0 , Ġ 1 ]` Ġallows Ġa Ġcontinu um Ġof Ġmodels Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbetween ĠL DA Ġand ĠQ DA . Ċ Ġ* Ġ@ param Ġprior i Ġthe Ġprior i Ġprobability Ġof Ġeach Ġclass . Ċ Ġ* Ġ@ param Ġtol Ġtolerance Ġto Ġdecide Ġif Ġa Ġcovariance Ġmatrix Ġis Ġsingular ; Ġit Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠ Ġwill Ġreject Ġvariables Ġwhose Ġvariance Ġis Ġless Ġthan Ġtol < sup > 2 </ sup >. Ċ Ġ* Ċ Ġ* Ġ@ return ĠRegular ized Ġdis crimin ant Ġanalysis Ġmodel . Ċ Ġ*/ Ċ fun Ġr da ( x : ĠArray < Double Array >, Ġy : ĠInt Array , Ġalpha : ĠDouble , Ġprior i : ĠDouble Array ? Ġ= Ġnull , Ġtol : ĠDouble Ġ= Ġ 0 . 0 0 0 1 ): ĠR DA Ġ{ ĊĠĠĠ Ġreturn ĠR DA . fit ( x , Ġy , Ġalpha , Ġprior i , Ġtol ) Ċ } Ċ Ċ /** Ċ Ġ* ĠCreates Ġa Ġna ive ĠBay es Ġclassifier Ġfor Ġdocument Ġclassification . Ċ Ġ* ĠAdd - k Ġsmoothing . Ċ Ġ* Ċ Ġ* Ġ@ param Ġx Ġtraining Ġsamples . Ċ Ġ* Ġ@ param Ġy Ġtraining Ġlabels Ġin Ġ`[ 0 , Ġk )`, Ġwhere Ġk Ġis Ġthe Ġnumber Ġof Ġclasses . Ċ Ġ* Ġ@ param Ġmodel Ġthe Ġgeneration Ġmodel Ġof Ġna ive ĠBay es Ġclassifier . Ċ Ġ* Ġ@ param Ġprior i Ġthe Ġprior i Ġprobability Ġof Ġeach Ġclass . ĠIf Ġnull , Ġequal Ġprobability Ġis Ġassume Ġfor Ġeach Ġclass . Ċ Ġ* Ġ@ param Ġsigma Ġthe Ġprior Ġcount Ġof Ġadd - k Ġsmoothing Ġof Ġevidence . Ċ Ġ*/ Ċ fun Ġna ive Bay es ( x : ĠArray < IntArray >, Ġy : ĠInt Array , Ġmodel : ĠDis crete Na ive Bay es . Model , Ġprior i : ĠDouble Array ? Ġ= Ġnull , Ġsigma : ĠDouble Ġ= Ġ 1 . 0 ): ĠDis crete Na ive Bay es Ġ{ ĊĠĠĠ Ġval Ġp Ġ= Ġx [ 0 ]. size ĊĠĠĠ Ġval Ġk Ġ= ĠMath Ex . max ( y ) Ġ+ Ġ 1 ĊĠĠĠ Ġval Ġlabels Ġ= ĠClass Labels . fit ( y ). labels ĊĠĠĠ Ġval Ġna ive Ġ= Ġif Ġ( pri ori Ġ== Ġnull ) ĊĠĠĠĠĠĠĠ ĠDis crete Na ive Bay es ( model , Ġk , Ġp , Ġsigma , Ġlabels ) ĊĠĠĠ Ġelse ĊĠĠĠĠĠĠĠ ĠDis crete Na ive Bay es ( model , Ġprior i , Ġp , Ġsigma , Ġlabels ) ĊĠĠĠ Ġna ive . update ( x , Ġy ) ĊĠĠĠ Ġreturn Ġna ive Ċ } Ċ Ċ /** Ċ Ġ* ĠCreates Ġa Ġgeneral Ġna ive ĠBay es Ġclassifier . Ċ Ġ* Ċ Ġ* Ġ@ param Ġprior i Ġthe Ġprior i Ġprobability Ġof Ġeach Ġclass . Ċ Ġ* Ġ@ param Ġcond prob Ġthe Ġconditional Ġdistribution Ġof Ġeach Ġvariable Ġin Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġeach Ġclass . ĠIn Ġparticular , Ġ` cond prob [ i ][ j ]` Ġis Ġthe Ġconditional Ċ Ġ* ĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdistribution ĠP ( x < sub > j </ sub > Ġ| Ġclass Ġi ). Ċ Ġ*/ Ċ fun Ġna ive Bay es ( pri ori : ĠDouble Array , Ġcond prob : ĠArray < Array < Distribution >> ): ĠNa ive Bay es Ġ{ Ċ return ĠNa ive Bay es ( pri ori , Ġcond prob ) Ċ } Ċ Ċ /** Ċ Ġ* ĠOne - vs - one Ġstrategy Ġfor Ġreducing Ġthe Ġproblem Ġof Ċ Ġ* Ġmult ic lass Ġclassification Ġto Ġmultiple Ġbinary Ġclassification Ġproblems . Ċ Ġ* ĠThis Ġapproach Ġtr ains ĠK Ġ( K ĠâĪ Ĵ Ġ 1 ) Ġ/ Ġ 2 Ġbinary Ġclassifiers Ġfor Ġa Ċ Ġ* ĠK - way Ġmult ic lass Ġproblem ; Ġeach Ġreceives Ġthe Ġsamples Ġof Ġa Ġpair Ġof Ċ Ġ* Ġclasses Ġfrom Ġthe Ġoriginal Ġtraining Ġset , Ġand Ġmust Ġlearn Ġto Ġdistinguish Ċ Ġ* Ġthese Ġtwo Ġclasses . ĠAt Ġprediction Ġtime , Ġa Ġvoting Ġscheme Ġis Ġapplied : Ċ Ġ* Ġall ĠK Ġ( K ĠâĪ Ĵ Ġ 1 ) Ġ/ Ġ 2 Ġclassifiers Ġare Ġapplied Ġto Ġan Ġun seen Ġsample Ġand Ġthe Ċ Ġ* Ġclass Ġthat Ġgot Ġthe Ġhighest Ġnumber Ġof Ġpositive Ġpredictions Ġgets Ġpredicted Ċ Ġ* Ġby Ġthe Ġcombined Ġclassifier . Ċ Ġ* ĠLike ĠOne - vs - rest , Ġone - vs - one Ġsuff ers Ġfrom Ġamb igu ities Ġin Ġthat Ġsome Ċ Ġ* Ġregions Ġof Ġits Ġinput Ġspace Ġmay Ġreceive Ġthe Ġsame Ġnumber Ġof Ġvotes . Ċ Ġ*/ Ċ fun Ġ< T > Ġo vo ( x : ĠArray < T >, Ġy : ĠInt Array , Ġtrainer : Ġ( Array < T >, ĠInt Array ) Ġ-> ĠClass ifier < T >): ĠOne Vers us One < T > Ġ{ ĊĠĠĠ Ġreturn ĠOne Vers us One . fit ( x , Ġy , Ġtrainer ) Ċ } Ċ Ċ /** Ċ Ġ* ĠOne - vs - rest Ġ( or Ġone - vs - all ) Ġstrategy Ġfor Ġreducing Ġthe Ġproblem Ġof Ċ Ġ* Ġmult ic lass Ġclassification Ġto Ġmultiple Ġbinary Ġclassification Ġproblems . Ċ Ġ* ĠIt Ġinvolves Ġtraining Ġa Ġsingle Ġclassifier Ġper Ġclass , Ġwith Ġthe Ġsamples Ċ Ġ* Ġof Ġthat Ġclass Ġas Ġpositive Ġsamples Ġand Ġall Ġother Ġsamples Ġas Ġneg atives . Ċ Ġ* ĠThis Ġstrategy Ġrequires Ġthe Ġbase Ġclassifiers Ġto Ġproduce Ġa Ġreal - valu ed Ċ Ġ* Ġconfidence Ġscore Ġfor Ġits Ġdecision , Ġrather Ġthan Ġjust Ġa Ġclass Ġlabel ; Ċ Ġ* Ġdiscrete Ġclass Ġlabels Ġalone Ġcan Ġlead Ġto Ġamb igu ities , Ġwhere Ġmultiple Ċ Ġ* Ġclasses Ġare Ġpredicted Ġfor Ġa Ġsingle Ġsample . Ċ Ġ* Ġ< p > Ċ Ġ* ĠMaking Ġdecisions Ġmeans Ġapplying Ġall Ġclassifiers Ġto Ġan Ġun seen Ġsample Ċ Ġ* Ġx Ġand Ġpredict ing Ġthe Ġlabel Ġk Ġfor Ġwhich Ġthe Ġcorresponding Ġclassifier Ċ Ġ* Ġreports Ġthe Ġhighest Ġconfidence Ġscore . Ċ Ġ* Ġ< p > Ċ Ġ* ĠAlthough Ġthis Ġstrategy Ġis Ġpopular , Ġit Ġis Ġa Ġhe uristic Ġthat Ġsuff ers Ċ Ġ* Ġfrom Ġseveral Ġproblems . ĠFirst ly , Ġthe Ġscale Ġof Ġthe Ġconfidence Ġvalues Ċ Ġ* Ġmay Ġdiffer Ġbetween Ġthe Ġbinary Ġclassifiers . ĠSecond , Ġeven Ġif Ġthe Ġclass Ċ Ġ* Ġdistribution Ġis Ġbal anced Ġin Ġthe Ġtraining Ġset , Ġthe Ġbinary Ġclassification Ċ Ġ* Ġlearn ers Ġsee Ġun balanced Ġdistributions Ġbecause Ġtypically Ġthe Ġset Ġof Ċ Ġ* Ġneg atives Ġthey Ġsee Ġis Ġmuch Ġlarger Ġthan Ġthe Ġset Ġof Ġposit ives . Ċ Ġ*/ Ċ fun Ġ< T > Ġo vr ( x : ĠArray < T >, Ġy : ĠInt Array , Ġtrainer : Ġ( Array < T >, ĠInt Array ) Ġ-> ĠClass ifier < T >): ĠOne Vers us Rest < T > Ġ{ ĊĠĠĠ Ġreturn ĠOne Vers us Rest . fit ( x , Ġy , Ġtrainer ) Ċ } Ċ