氟離子選擇電極使用及氟離子濃度測量

IntroductiontoInformationRetrieval

IntroductiontoInformationRetrievalCS276:InformationRetrievalandWebSearchTextClassification1ChrisManning,PanduNayakandPrabhakarRaghavanIntroductiontoInformationRetrieval

PrepworkThislecturepresumesthatyou’veseenthe124courseralectureonNa?veBayes,orequivalentWillrefertoNBwithoutdescribingitCh.13IntroductiontoInformationRetrieval

StandingqueriesThepathfromIRtotextclassification:Youhaveaninformationneedtomonitor,say:UnrestintheNigerdeltaregionYouwanttorerunanappropriatequeryperiodicallytofindnewnewsitemsonthistopicYouwillbesentnewdocumentsthatarefoundI.e.,it’snotrankingbutclassification(relevantvs.notrelevant)SuchqueriesarecalledstandingqueriesLongusedby“informationprofessionals”AmodernmassinstantiationisGoogleAlertsStandingqueriesare(hand-written)textclassifiersCh.13IntroductiontoInformationRetrieval

3IntroductiontoInformationRetrieval

Spamfiltering

AnothertextclassificationtaskFrom:""<takworlld@>Subject:realestateistheonlyway...gemoalvgkayAnyonecanbuyrealestatewithnomoneydownStoppayingrentTODAY!ThereisnoneedtospendhundredsoreventhousandsforsimilarcoursesIam22yearsoldandIhavealreadypurchased6propertiesusingthemethodsoutlinedinthistrulyINCREDIBLEebook.ChangeyourlifeNOW!=================================================ClickBelowtoorder:/sales/nmd.htm=================================================Ch.13IntroductiontoInformationRetrieval

Categorization/ClassificationGiven:ArepresentationofadocumentdIssue:howtorepresenttextdocuments.Usuallysometypeofhigh-dimensionalspace–bagofwordsAfixedsetofclasses:

C={c1,c2,…,cJ}Determine:Thecategoryofd:γ(d)∈C,whereγ(d)isaclassificationfunctionWewanttobuildclassificationfunctions(“classifiers”).Sec.13.1IntroductiontoInformationRetrieval

MultimediaGUIGarb.Coll.SemanticsMLPlanningplanningtemporalreasoningplanlanguage...programmingsemanticslanguageproof...learningintelligencealgorithmreinforcementnetwork...garbagecollectionmemoryoptimizationregion...“planninglanguageproofintelligence”TrainingData:TestData:Classes:(AI)DocumentClassification(Programming)(HCI)......Sec.13.1IntroductiontoInformationRetrieval

ClassificationMethods(1)ManualclassificationUsedbytheoriginalYahoo!DirectoryLooksmart,,ODP,PubMedAccuratewhenjobisdonebyexpertsConsistentwhentheproblemsizeandteamissmallDifficultandexpensivetoscaleMeansweneedautomaticclassificationmethodsforbigproblemsCh.13IntroductiontoInformationRetrieval

ClassificationMethods(2)Hand-codedrule-basedclassifiersOnetechniqueusedbynewagencies,intelligenceagencies,etc.WidelydeployedingovernmentandenterpriseVendorsprovide“IDE”forwritingsuchrulesCh.13IntroductiontoInformationRetrieval

ClassificationMethods(2)Hand-codedrule-basedclassifiersCommercialsystemshavecomplexquerylanguagesAccuracyiscanbehighifarulehasbeencarefullyrefinedovertimebyasubjectexpertBuildingandmaintainingtheserulesisexpensiveCh.13IntroductiontoInformationRetrieval

AVeritytopic

AcomplexclassificationruleNote:maintenanceissues(author,etc.)Hand-weightingofterms[VeritywasboughtbyAutonomy,whichwasboughtbyHP...]Ch.13IntroductiontoInformationRetrieval

ClassificationMethods(3):

SupervisedlearningGiven:AdocumentdAfixedsetofclasses:

C={c1,c2,…,cJ}Atrainingset

DofdocumentseachwithalabelinCDetermine:AlearningmethodoralgorithmwhichwillenableustolearnaclassifierγForatestdocumentd,weassignittheclassγ(d)∈CSec.13.1IntroductiontoInformationRetrieval

ClassificationMethods(3)SupervisedlearningNaiveBayes(simple,common)–seevideok-NearestNeighbors(simple,powerful)Support-vectormachines(new,generallymorepowerful)…plusmanyothermethodsNofreelunch:requireshand-classifiedtrainingdataButdatacanbebuiltup(andrefined)byamateursManycommercialsystemsuseamixtureofmethodsCh.13IntroductiontoInformationRetrieval

ThebagofwordsrepresentationIlovethismovie!It'ssweet,butwithsatiricalhumor.Thedialogueisgreatandtheadventurescenesarefun…Itmanagestobewhimsicalandromanticwhilelaughingattheconventionsofthefairytalegenre.Iwouldrecommendittojustaboutanyone.I'veseenitseveraltimes,andI'malwayshappytoseeitagainwheneverIhaveafriendwhohasn'tseenityet.γ()=cIntroductiontoInformationRetrieval

Thebagofwordsrepresentationγ()=cgreat2love2recommend1laugh1happy1......IntroductiontoInformationRetrieval

FeaturesSupervisedlearningclassifierscanuseanysortoffeatureURL,emailaddress,punctuation,capitalization,dictionaries,networkfeaturesInthebagofwordsviewofdocumentsWeuseonlywordfeaturesweuseallofthewordsinthetext(notasubset)IntroductiontoInformationRetrieval

FeatureSelection:Why?Textcollectionshavealargenumberoffeatures10,000–1,000,000uniquewords…andmoreSelectionmaymakeaparticularclassifierfeasibleSomeclassifierscan’tdealwith1,000,000featuresReducestrainingtimeTrainingtimeforsomemethodsisquadraticorworseinthenumberoffeaturesMakesruntimemodelssmallerandfasterCanimprovegeneralization(performance)EliminatesnoisefeaturesAvoidsoverfittingSec.13.5IntroductiontoInformationRetrieval

FeatureSelection:FrequencyThesimplestfeatureselectionmethod:JustusethecommonesttermsNoparticularfoundationButitmakesensewhythisworksThey’rethewordsthatcanbewell-estimatedandaremostoftenavailableasevidenceInpractice,thisisoften90%asgoodasbettermethodsSmarterfeatureselection–futurelectureIntroductiontoInformationRetrieval

EvaluatingCategorizationEvaluationmustbedoneontestdatathatareindependentofthetrainingdataSometimesusecross-validation(averagingresultsovermultipletrainingandtestsplitsoftheoveralldata)Easytogetgoodperformanceonatestsetthatwasavailabletothelearnerduringtraining(e.g.,justmemorizethetestset)Sec.13.6IntroductiontoInformationRetrieval

EvaluatingCategorizationMeasures:precision,recall,F1,classificationaccuracyClassificationaccuracy:r/nwherenisthetotalnumberoftestdocsandristhenumberoftestdocscorrectlyclassifiedSec.13.6IntroductiontoInformationRetrieval

WebKBExperiment(1998)ClassifywebpagesfromCSdepartmentsinto:student,faculty,course,projectTrainon~5,000hand-labeledwebpagesCornell,Washington,U.Texas,WisconsinCrawlandclassifyanewsite(CMU)usingNa?veBayesResultsSec.13.6IntroductiontoInformationRetrieval

IntroductiontoInformationRetrieval

SpamAssassinNa?veBayeshasfoundahomeinspamfilteringPaulGraham’sAPlanforSpamWidelyusedinspamfiltersButmanyfeaturesbeyondwords:blackholelists,etc.particularhand-craftedtextpatternsIntroductiontoInformationRetrieval

SpamAssassinFeatures:Basic(Na?ve)BayesspamprobabilityMentions:GenericViagraRegex:millionsof(dollar)((dollar)NN,NNN,NNN.NN)Phrase:impress...girlPhrase:‘PrestigiousNon-AccreditedUniversities’From:startswithmanynumbersSubjectisallcapitalsHTMLhasalowratiooftexttoimageareaRelayinRBL,/enduserinfo_rbl.htmlRCVDlinelooksfaked/tests_3_3_x.htmlIntroductiontoInformationRetrieval

NaiveBayesisNotSoNaiveVeryfastlearningandtesting(basicallyjustcountwords)LowstoragerequirementsVerygoodindomainswithmanyequallyimportantfeaturesMorerobusttoirrelevantfeaturesthanmanylearningmethods IrrelevantfeaturescanceleachotherwithoutaffectingresultsIntroductiontoInformationRetrieval

NaiveBayesisNotSoNaiveMorerobusttoconceptdrift(changingclassdefinitionovertime)NaiveBayeswon1stand2ndplaceinKDD-CUP97competitionoutof16systems Goal:Financialservicesindustrydirectmailresponseprediction:Predictiftherecipientofmailwillactuallyrespondtotheadvertisement–750,000records.Agooddependablebaselinefortextclassification(butnotthebest)!IntroductiontoInformationRetrieval

ClassificationUsingVectorSpacesInvectorspaceclassification,trainingsetcorrespondstoalabeledsetofpoints(equivalently,vectors)Premise1:DocumentsinthesameclassformacontiguousregionofspacePremise2:Documentsfromdifferentclassesdon’toverlap(much)Learningaclassifier:buildsurfacestodelineateclassesinthespace28DocumentsinaVectorSpaceGovernmentScienceArtsSec.14.129TestDocumentofwhatclass?GovernmentScienceArtsSec.14.130TestDocument=GovernmentGovernmentScienceArtsIsthissimilarityhypothesistrueingeneral?Ourfocus:howtofindgoodseparatorsSec.14.1DefinitionofcentroidWhereDc

isthesetofalldocumentsthatbelongtoclasscandv(d)isthevectorspacerepresentationofd.Notethatcentroidwillingeneralnotbeaunitvectorevenwhentheinputsareunitvectors.31Sec.14.2RocchioclassificationRocchioformsasimplerepresentativeforeachclass:thecentroid/prototypeClassification:nearestprototype/centroidItdoesnotguaranteethatclassificationsareconsistentwiththegiventrainingdata32Sec.14.2RocchioclassificationLittleusedoutsidetextclassificationIthasbeenusedquiteeffectivelyfortextclassificationButingeneralworsethanNa?veBayesAgain,cheaptotrainandtestdocuments33Sec.14.234kNearestNeighborClassificationkNN=kNearestNeighborToclassifyadocumentd:Definek-neighborhoodastheknearestneighborsofdPickthemajorityclasslabelinthek-neighborhoodSec.14.335Example:k=6(6NN)GovernmentScienceArtsP(science|)?Sec.14.336Nearest-NeighborLearningLearning:juststorethelabeledtrainingexamplesDTestinginstancex(under1NN):ComputesimilaritybetweenxandallexamplesinD.AssignxthecategoryofthemostsimilarexampleinD.DoesnotcomputeanythingbeyondstoringtheexamplesAlsocalled:Case-basedlearningMemory-basedlearningLazylearningRationaleofkNN:contiguityhypothesisSec.14.337kNearestNeighborUsingonlytheclosestexample(1NN)subjecttoerrorsdueto:Asingleatypicalexample.Noise(i.e.,anerror)inthecategorylabelofasingletrainingexample.Morerobust:findthekexamplesandreturnthemajoritycategoryofthesekkistypicallyoddtoavoidties;3and5aremostcommonSec.14.338kNNdecisionboundariesGovernmentScienceArtsBoundariesareinprinciplearbitrarysurfaces–butusuallypolyhedrakNNgiveslocallydefineddecisionboundariesbetweenclasses–farawaypointsdonotinfluenceeachclassificationdecision(unlikeinNa?veBayes,Rocchio,etc.)Sec.14.339Illustrationof3NearestNeighborforTextVectorSpaceSec.14.3403NearestNeighborvs.RocchioNearestNeighbortendstohandlepolymorphiccategoriesbetterthanRocchio/NB.41kNN:DiscussionNofeatureselectionnecessaryNotrainingnecessaryScaleswellwithlargenumberofclassesDon’tneedtotrainnclassifiersfornclassesClassescaninfluenceeachotherSmallchangestooneclasscanhaverippleeffectMaybeexpensiveattesttimeInmostcasesit’smoreaccuratethanNBorRocchioSec.14.3Let’stestourintuitionCanabagofwordsalwaysbeviewedasavectorspace?Whataboutabagoffeatures?Canwealwaysviewastandingqueryasaregioninavectorspace?WhataboutBooleanqueriesonterms?Whatdo“rectangles”equateto?4243Biasvs.capacity–notionsandterminologyConsideraskingabotanist:Isanobjectatree?