Payne644
644 时间:2021-01-17 阅读:()
(12)UnitedStatesPatentCaoeta].
US007644074B2(10)PatentN0.
:(45)DateofPatent:US7,644,074B2Jan.
5,2010(54)(75)(73)(21)(22)(65)(51)(52)SEARCHBYDOCUMENTTYPEANDRELEVANCEInventors:YunboCa0,Beijing(CN);HangLi,Beijing(CN);JunXu,Tianjin(CN)(58)FieldofClassicationSearch707/100Seeapplicationleforcompletesearchhistory.
(56)ReferencesCitedU.
S.
PATENTDOCUMENTS___2005/0182783A1*8/2005Vadaieta1.
.
.
707/102Ass1gnee:MicrosoftCorporation,Redmond,WA2005/0246314A1>ilDisk''\5ProgramMLIGSJ/ProcessingRAMProgramUnit'IIIIII|I|=EEROMtL50]HOInterfaces505'-506HODevicepegrpicg'al503504500US7,644,074B21SEARCHBYDOCUMENTTYPEANDRELEVANCEBACKGROUNDThisdescriptionrelatesgenerallytocomputeraidedsearchingandmorespecicallytosearchingforinstructiondocuments.
Peopleoftenfaceunfamiliartasks,andthustheyneedappropriateinstructionsforconductingthem.
MuchefforthasbeenmadetocopeWiththeproblem.
Includingbooksforpopular'hoW-to'questions.
ManyonlineservicesforansWeringhoW-toquestionsarealsoavailableWhichcanmaintainalargecollectionofinstructiondocumentsandprovideasearchserviceonthecollection.
However,noneofthemtypicallycancoverallofthehoWtoquestionsindailylife.
Thus,itcouldbehelpfultohaveasystemthathelpsautomaticallyretrieve'instructions'(i.
e.
,documentsoftaskguides)ontheWeb(eitherInternetorintranet).
SUMMARYThefolloWingpresentsasimpliedsummaryofthedisclosureinordertoprovideabasicunderstandingtothereader.
ThissummaryisnotanextensiveovervieWofthedisclosureanditdoesnotidentifykey/criticalelementsoftheinventionordelineatethescopeoftheinvention.
Itssolepurposeistopresentsomeconceptsdisclosedhereininasimpliedformasapreludetothemoredetaileddescriptionthatispresentedlater.
ThepresentexampleprovidesaWaytosearchformanualsorotherdocumentsbycombiningarelevancemodelandatypemodel.
Trainingdataisprovidedtoeachmodelandthemodelisthenappliedtoarstpluralityofdocuments.
TWocollectionsofdocumentsresult.
Arstcollectionrankedbytype,andasecondcollectionrankedbyrelevance.
Throughalinearinterpolationthedocumentsarecombinedtoproduceasecondpluralityofdocumentsrankedbyrelevanceandtype.
ManyoftheattendantfeaturesWillbemorereadilyappreciatedasthesamebecomesbetterunderstoodbyreferencetothefolloWingdetaileddescriptionconsideredinconnectionWiththeaccompanyingdraWings.
DESCRIPTIONOFTHEDRAWINGSThepresentdescriptionWillbebetterunderstoodfromthefolloWingdetaileddescriptionreadinlightoftheaccompanyingdraWings,Wherein:FIG.
1shoWstWoexamplesofWebdocumentsthatmaybefoundinaconventionalsearch.
FIG.
2shoWstWoexemplaryinstructiondocumentsfoundastheresultofaconventionalsearchpertainingtothequery'hoWtocompileAmaya'.
FIG.
3shoWsexamplesofdocumentsthatmightbefoundasaresultofasearch.
FIG.
4isaHowdiagramshoWingmanualssearchbyusingarelevancemodelandatypemodel.
FIG.
5illustratesanexemplarycomputingenvironment500inWhichthemanualssearchbyusingarelevancemodelandatypemodeldescribedinthisapplication,maybeimplemented.
LikereferencenumeralsareusedtodesignatelikepartsintheaccompanyingdraWings.
202530354045505560652DETAILEDDESCRIPTIONThedetaileddescriptionprovidedbeloWinconnectionWiththeappendeddraWingsisintendedasadescriptionofthepresentexamplesandisnotintendedtorepresenttheonlyformsinWhichthepresentexamplemaybeconstructedorutiliZed.
Thedescriptionsetsforththefunctionsoftheexampleandthesequenceofstepsforconstructingandoperatingtheexample.
HoWever,thesameorequivalentfunctionsandsequencesmaybeaccomplishedbydifferentexamples.
TheexamplesbeloWdescribeamanualssearchbyusingarelevancemodelandatypemodel.
Althoughthepresentexamplesaredescribedandillustratedhereinasbeingimplementedinaninstructionmanualsearchsystem,thesystemdescribedisprovidedasanexampleandnotalimitation.
AsthoseskilledintheartWillappreciate,thepresentexamplesaresuitableforapplicationinavarietyofdifferenttypesofsearchsystems.
Traditionalinformationretrievaltypicallyaimsatndingrelevantdocuments.
HoWever,relevantdocumentsfoundinthismannerarenotnecessarilyinstructiondocuments,i.
e.
,ansWerstohoW-toquestions.
Thus,anaiveapplicationofthetraditionalinformationretrievalmaynotproducethedesiredinstructions.
InthefolloWingexample,investigationofquestionansWeringinaneWsettingisprovidedbyamethodcalled"manualssearch".
Morespecically,givenahoW-toquery,alldocumentsmaybeautomaticallyretrievedandrankedWhicharerelevanttothequeryandWhicharealsolikelytobeaninstructiondocument.
Inparticularthetrainingtypemanualisinterpreted,orseen,asaclassicationproblem.
Andthemethodoffusingscoresfromthetypemodelandtherelevancemodelmaybedonebylinearlyinterpolatingthescores.
TheexamplesbeloWprovideamanualssearchprocesstypicallyutiliZingarelevancemodelandatypemodel.
Specically,Whengivena'hoW-to'typeofquery(e.
g.
,'hoWtocreatealink'),documentsareretrievedandrankedthemaccordingtoboththelikelihoodofbeinganinstructiondocument(adocumentcontainingdescriptionabouthoWtoperformatask)andtherelevancetothequery.
Traditionaldocumentretrievaltypicallyonlyconsiderstherelevanceofdocumentstoqueries.
ThemethodofperformingthetaskmayincludeWhatmaybereferredtohereas'relevancemodel'and'typemodel'.
Withtherelevancemodel,itisdeterminedWhetherornotadocumentisrelevanttoaquery.
Withthetypemodel,itisdeterminedWhetherornotadocumentisaninstructiondocument.
OkapiandLogisticRegressionmaybeemployedastherelevancemodelandthetypemodel,respectively.
AmethodforcombiningtheusesofthetWomodelsbasedonlinearinterpolationisalsoproposed.
Intheexampleprovidedthemethodisdescribedintermsofamanualssearch.
Morespecically,givenahoW-toquery,documentsWhicharerelevanttothequeryandWhicharelikelytobeinstructiondocumentsareretrievedandranked.
Themanualssearchisbasedonarelevancemodelandatypemodel.
OkapimaybeemployedastherelevancemodelandLogisticRegressionasthetypemodel,respectively.
Amethodbasedonalinearinterpolationtechniqueisalsoproposedtofusetheoutputoftherelevancemodelandthetypemodel.
TheinstantmanualssearchtypicallyperformsWellonbotharticialdatasetsandrealdatasets.
ForhoW-toqueries,goodinstructiondocumentsareoftenrankedhigherusingtheexemplaryapproachthanthebaselinemethodofeithersolelyusingOkapiorsolelyusingLogisticRegression.
TheproposedapproachtypicallyperformsWellondifferentdomains.
US7,644,074B23Theexampleprovidedofamethodofmanualssearchmaybebasedonarelevancemodelandatypemodel.
InparticularOkapimaybeemployedastherelevancemodelandLogisticRegressionasthetypemodel,respectively.
Okapiisasystemfordocumentretrievalbasedonaprobabilisticmodel.
Itretrievesandranksdocumentsaccordingtotherelevanceofdocumentstoqueries.
Okapioritsequivalentmaybeemployedintheexampleprovided.
OkapiisdescribedmorefullybyS.
E.
Robertson,S.
Walker,M.
M.
Beaulieu,M.
Gatford,andA.
Payne.
OkapiatTREC-4.
InD.
K.
Harman,editor,TheFourthTextRetrievalConference(TREC-4),pages73-96,Gaithersburg,Md.
,1996.
NationalInstituteofStandardsandTechnology,SpecialPublication500-236.
LogisticRegressionisaprobabilisticclassicationmodelmorefullydescribedinT.
Hastie,R.
Tibshirani,andJ.
Friedman.
TheElementsofStatisticalLearning.
Springer,N.
Y.
,2001.
IncontrasttootherclassicationmodelssuchasSupportVectorMachine(SVM),LogisticRegressiontypicallyoutputsprobabilityvaluesratherthanscoresinclassication.
AmethodbasedonalinearinterpolationtechniqueisalsoutiliZedtofusetheoutputoftherelevancemodelandthetypemodel.
Amanualssearchmaybemorehelpfulthanaconventionalsearchthattendstoreturnagreaterrangeofresults,manyofWhicharenotinstructions.
Inperformingamanualssearchaqueryistypicallyreceivedrst.
ThequeryisusuallyahoW-toquestion,e.
g.
,'hoWtocreatealink'.
Nextusingconventionalmethodsautomaticretrievalofalloftherelevantandlikelyinstructiondocumentsisperformed.
Next,thedocumentsmayberankedaccordingtothedegreeoflikelihoodofbeinganinstructiondocumentandthedegreeofrelevancetothequery.
ManualssearchtypicallyneedstoassurethattheretrieveddocumentsarerelevanttothequeriesasWell.
HoWever,incontrast,manualssearchmayalsoneedtoassurethattheretrieveddocumentsareinstructiondocuments.
Table1shoWspossiblesetsofdocumentsthatmaybesearchedfor.
FromTable1,Aisthesetthatistypicallydesiredinmanualssearch.
Cisthesetthatisrelevantbutnon-instructionandthusshouldbelteredout.
TABLE1TWovieWsofdocumentsRelevantIrrelevantInstructionABNon-instructionCDFIG.
1shoWstWoexamplesofWebdocumentsthatmaybefoundinaconventionalsearch.
Therstdocument101isnotaninstructiondocumentandtheseconddocument102isaninstructiondocument.
Thus,ifthequeryis'hoWtocreatealink',thentheseconddocument102Wouldbepreferredbyusers.
HoWever,ifonlyrelevanceisconsidered,thentherstdocument101Willlikelyberankedhigher,becauseitWouldtypicallyappeartobemorerelevanttothequery.
QuestionansWeringmaybeidealforaccessinginformationoninstructions,ifrealiZed,becauseitsgoalistoprovideasinglecombinedansWer.
OnecansimplygetallthenecessaryinformationbyreadingthecombinedansWer.
HoWever,generationofsuchacombinedansWermaybeverychallengingorevenimpossibleforcurrentsystems.
First,mostansWerstoahoWtoqueryconsistofstep-by-stepguidesastheexampleshoWnintheseconddocumentinFIG.
2.
Deletions,insertions,orre-orderingsmadeinanypartofthedocumentmayconfuseormisguidetypicalsearches.
Second,differentinstruction202530354045505560654documentsmayhavedifferentassumptionsandsettings,evenforthesametopic.
Thusitmaynotbeappropriatetocombinetheinstructionsbasedondifferentassumptionsandsettings.
FIG.
2shoWstWoexemplaryinstructiondocumentsfoundastheresultofaconventionalsearchpertainingtothequery'hoWtocompileAmaya'.
HoWever,theyprovideinstructionsfordifferentsettings.
Onedocument201providesinstructions'WithAutoconf'settings.
Theotherdocument202providesinstructionsWithWindoWs'settings.
Therefore,areasonableapproachWouldbetoshoWuserstheinstructiondocumentsseparately.
AsseenabovejudgingWhetheradocumentisarelevantinstructiondocument,andthuscanbeusedasanansWertoahoW-toqueryinanobjectiveWaymaybehard.
HoWever,Wecanstillproviderelativelyobjectiveguidelinesforthejudgment.
TheobjectiveguidelinesWillbetermedthespecicationinthisfolloWingdescription.
Thespecicationmaybeusedextensivelyfordevelopmentandevaluationofthemanualssearchprocess.
AspreviouslyshoWninTable1,thespecicationcanbedesignedfromtWovieWpoints.
Forthenotionofrelevance,specicationmaybedenedinasimilarfashionasthatintraditionalinformationretrieval.
Indoingsothenotionofinstructionisclariedrst.
FIG.
3shoWsexamplesofdocuments301302303thatmightbefoundasaresultofasearch.
First,aninstructiondocumentisadocumentcreatedforansWeringahoW-toquery.
Morespecically,byreadingthedocument,onecanunderstandhoWtoperformthetaskofthehoW-toquery.
Second,intheexampleprovided,aninstructiondocumentisassumednottobeadocumentcontaininginstructionsforanumberofdifferenttasks.
Forexample,therstdocumentinFIG.
4isnotregardedasaninstructiondocument.
Third,intheexampleprovided,aninstructiondocumentisassumednottobeadocumentthatonlyconsistspartlyofinstructions.
Forexample,theseconddocument302isnotvieWedasaninstructiondocument,becauseasectionofitisabouthoW-to.
Ascanbeseenfromtheabovediscussionsomeinstructiondocumentsmaycontainstep-by-stepguides(cf.
,theseconddocumentinFIG.
2);Whileotherinstructiondocumentsmayjustconsistofseveralsentences(e.
g.
,thelastdocumentinFIG.
4).
Thecriteriausedabovemaybequantiedforuseinamanualssearch.
Withthespecicationdenedabove,fourlabelssimilartothoseinTable1areprovided.
Forthepurposesofmanualssearch,hoWever,thereshouldbenodifferencebetWeenthelabelsCandD.
Thus,WecombineCandDtogethertoC-D.
Inmanualssearch,givenaqueryqandadocumentd,oneofthethreelabelsbeloWcanbeassigned:A:documentdisrelevanttoqandisaninstructiondocumentB:documentdisirrelevanttoqbutisaninstructiondocumentC-D:documentdisofnouseFIG.
4isaHowdiagramshoWingmanualssearchbyusingarelevancemodel401andatypemodel402.
Intheexampleprovidedofmanualssearchbyusingarelevancemodelandatypemodeltheinputmaybeaquery403andacollectionofdocuments404.
Thedocumentsmayhaveresultedfromaconventionalsearch,ormaysimplybeacollectionofdocumentstobeexamined.
TheexemplaryapproachtomanualssearchincludestWosteps.
First,arepresentationtorelevancetoaqueryandalikelihoodofbeinganinstructiondocumentisformedWithtWosub-models,WhichWecalla'relevancemodel'401anda'typemodel'402,respectively.
Intherelevancemodel,itisjudgedWhetherornotadocumentintheinputisrelevanttothequery407.
Inthetypemodel,itisjudgedWhetherornotadocumentintheinputisaninstrucUS7,644,074B25tiondocument408.
Next,alinearinterpolationtechniquemaybeusedtocombinethescoresoutputfromthetWosub-models405.
Thedocumentsarethenrankedindescendingorderoftheircombinedscores406.
AsshoWntrainingdatamaybesuppliedingeneraltoatrainingrelevancemodel.
However,trainingdataisnotneededWiththeexemplaryOkapiBM25modelorothertypesofrelevancemodelsthatmaybeutilizedinplaceofOkapiBM25.
Intheexampleprovidedtrainingdatamayalsobesuppliedtothetypemodel,hoWeveritisanticipatedthatinsomeapplicationstrainingdatamaynotbeneeded.
RelevanceModel(Okapi)GivenahoW-toqueryandadocument,therelevancemodelndsarelevancescore.
Inmanualssearch,foragivenquery,alistofpairsusingtherelevancemodeltogeneratetherelevancescorearecreated.
InthepresentexampletheOkapiBM25relevancescoremaybeemployedastherelevancemodel.
Forindexingthetitleandthebodyofadocumentareindexedinseparateelds.
Foreacheld,theOkapiBM25Weightingschemeisusedtocalculateascore.
Thenthescoresofthetitleeldandthebodyeldarecombinedlinearly,andthecombinedscoreisvieWedastherelevance-score.
TypeModel(LogisticRegression)Givenadocument,thetypemodeloutputsatypescore.
ThatmeansthatWeassumethatthetypemodelisindependentfromqueries.
Inmanualssearch,Wecreatealistofpairsusingthetypemodel.
Wetakeastatisticalmachinelearningapproachtoconstructingatypemodel.
Morespecically,givenatrainingdatasetD:{xi,yi}l",WeconstructamodelPr(y|x)thatcanminimizetheerrorinpredictingofygivenx(generalizationerror).
Herexi6Xandyl-e{l,—lxrepresentsadocumentandyrepresentsWhetherornotadocumentisaninstructiondocument.
WhenappliedtoaneWdocumentx,themodelpredictsthecorrespondingyandoutputsthescoreoftheprediction.
Inthisexample,WeadopttheLogisticRegressionModel.
LogisticRegressionTheLogisticRegressionModelsatises:Where[3representsthecoefcientsofalinearcombinationfunctionand[30istheintercept.
TheLogisticRegressionModelisusuallyestimatedbyusingMaximumLikelihood.
TheLogisticRegressionModelassignsaprobabilitytoaninstance(inourcaseadocument)probabilityaccordingtothefolloWingequation.
Wecalculatethetype-scoreofadocumentaccordingto:Pr(y=1IX)typeiscore:logm(3)202530354045505560656FeaturesTheLogisticRegressionModelutilizesbinaryorrealvaluedfeaturesasdescribedbeloW.
Mostfeaturesarecreatedtocharacterizetitle,rstheadingandrstsentenceofdocuments.
AlthoughthoseskilledintheartWillrealizethatinalternativeexamplesfeaturesarenotlimitedtocharacterizationsoftitlesheadingsentencesandthelike.
TitleisthetextenclosedbytheHTMLtag''and''.
HeadingisthetextenclosedbytheHTMLtag''and''.
Firstheadingreferstotherstnon-emptyheadingofaHTMLdocument.
FirstsentenceistherstsentenceappearinginthebodyofaHTMLdocument.
'HoWTo'WhetherornotthetitleofadocumentcontainstheWordsof'hoWto','hoWto'or'hoW-to'isanimportantindicator.
Thisisrepresentedusingabinaryfeature.
TherearesimilarfeaturesWithregardtotherstheadingandtherstsentenceofadocument.
ThoseskilledintheartWillrealizethatinalternativeexamplesofknoWledgeextractionotherWordsorphrasesofinterestmaybeidentiedandusedasimportantindicators.
'DoingSomething'Theappearanceofthesufx'ing'intherstWordofthetitleisanotherindicatorofaninstructiondocument.
Sometimespeopleusethetemplateof'doingsomething'insteadof'hoWtodosomething'forthetitleofaninstructiondocument.
Thevalueofthefeatureisbinary,too.
Similarfeatureshavealsobeendenedfortherstheadingandtherstsentence.
ThoseskilledintheartWillrealizethatotherWordsorWordfragmentsfromthetitlemaybeuseddependinguponthespecicapplicationofsearchbyusingarelevancemodelandatypemodel.
TextLengthAlsodenedisthefolloWingreal-valuedfeature:log(length(title)+l)(4)Wherelength(title)denotesthenumberofWordsinthetitle.
AdocumentWithashorttitle(egaone-Wordtitle)tendstobeanon-instructiondocument.
Similarfeatureshavealsobeendenedfortherstheadingandtherstsentence.
IdenticalExpressionsIfthetextsinanytWoofthethreeparts:title,rstheadingandrstsentenceareidentical,thenthisfeatureis1.
OtherWise,itis0.
Aninstructiondocumentusuallyrepeatsitstopicinthesethreeplaces.
BagofWordsAlsorelieduponare'bag-of-Words'features.
ThemethodcollectshighfrequencyWordsinthetitlesofthedocumentsintrainingdataandcreateabagofthekeyWords.
SomekeyWordsplaypositiveroles(e.
g.
,'troubleshoot','Wizards')andsomenegativeones(e.
g.
,'contact').
IfthetitleofadocumentcontainsoneofthekeyWords,thenthecorrespondingfeatureWillbe1,otherWise0.
Similarfeatureshavebeendenedfortherstheadingandtherstsentence.
CombinationofRelevanceandTypeModelsAranking_scoremaybecalculatedbylinearlyinterpolatingtherelevance_scoreandtype_scoreastheEquation(5).
rankingscore:7vtypeiscore+(l—7t)-relevanceiscore(5)Here,7e[0,l]isaWeightusedtobalancethecontributionoftherelevancemodelandthetypemodel.
AsWillbeexplainedlateritistypicallybettertohave7:0.
5Inmanualssearch,documentsareretrievedandrankedindescendingorderoftheranking_score.
US7,644,074B27Inprinciple,givenaqueryandadocumentcollection,onecancalculatetherankingscoreofeachofthedocumentsWithrespecttothequery.
Inanimplementationofthemethod,thetop100documentsrankedbytherelevancemodel(Okapi)arerstcollected.
Nextrankingscoresarecalculatedonlyforthetop100documents.
InthisWay,amanualssearchmaybeconductedveryefciently.
GeneralizationManualssearchmaybeformalizedinamoregeneralframeworkcalled'typedsearch'.
Intypedsearch,documentsareretrievedandrankednotonlyonthebasisofrelevancetothequery,butalsothelikelihoodofbeingthedesiredtype.
Givenaqueryqandadocumentd,WecalculatetherankingscoreofthepairusingEquation(6):Pr(r,llq,d)=Pr(rlq,d)-Pr(lld)(6)Whererandtdenoterelevanceandtype,respectively.
Bothrandtarebinaryvariables.
Inmanualsearch,forexample,tmeansthatadocumentisaninstructiondocument.
Intheequation,Wemakeanassumptionthatrandtgivenaqanddareindependent.
Therearemany'types'thatcanbeconsideredsuchasdenition,letter,andhomepage,forexample.
Inmanualssearch,onecandenetherelevancescoreandthetypescoreaslogoddsofPr(r|q,d)andPr(t|d),respectively(cf.
,Equation(3)).
ThisjustiesWhyWemakeuseofequalWeightinthelinearcombinationinEquation(5).
Kraajjetal.
haveproposedusingLanguageModelinthetaskofhome/namedpagending.
TheyemployamodelasfolloWs,Whichassignsascoretoapagedgivenaqueryq:TherstmodelontherighthandsideofEquation(7),correspondstothetypemodelinEquation(6)andthesecondmodelcorrespondstotherelevancemodel.
Therefore,homepagendingcanbevieWedasaspecializationoftypedsearch.
ForfurtherinformationonusingaLanguageModelseeW.
Kraajj,T.
WesterveldandD.
Hiemstra.
TheImporlanceofPriorProbabililiesforEnlryPageSearch.
InProc.
ofthe25thannualinternationalACMSIGIRconferenceonresearchanddevelopmentininformationretrieval,2002.
ThecontentsofWhichareincorporatedinthispatentapplicationintheirentirety,ConclusionsInmanualssearchthedocumentshavebeenrankedbycombiningarelevancemodelandatypemodel.
OkapiandLogisticRegressionhavebeenusedastherelevancemodelandthetypemodel,respectively.
FinalrankingscoresarethenobtainedbylinearlyinterpolatingthescoresfromthetWomodels.
TheproposedmethodmaybegeneralizedinageneralframeWorkcalledtypedsearch.
FIG.
5illustratesanexemplarycomputingenvironment500inWhichthemanualssearchbyusingarelevancemodelandatypemodeldescribedinthisapplication,maybeimplemented.
Exemplarycomputingenvironment500isonlyoneexampleofacomputingsystemandisnotintendedtolimittheexamplesdescribedinthisapplicationtothisparticularcomputingenvironment.
Forexamplethecomputingenvironment500canbeimplementedWithnumerousothergeneralpurposeorspecialpurposecomputingsystemcongurations.
ExamplesofWellknoWncomputingsystems,mayinclude,butarenotlimitedto,personalcomputers,hand-heldorlaptopdevices,microprocessor-basedsystems,multiprocessorsystems,settopboxes,gamingconsoles,consumerelectronics,cellulartelephones,PDAs,andthelike.
2030354045505560658Thecomputer500includesageneral-purposecomputingsystemintheformofacomputingdevice501.
Thecomponentsofcomputingdevice501canincludeoneormoreprocessors(includingCPUs,GPUs,microprocessorsandthelike)507,asystemmemory509,andasystembus508thatcouplesthevarioussystemcomponents.
Processor507processesvariouscomputerexecutableinstructions,includingthoseto**tocontroltheoperationofcomputingdevice501andtocommunicateWithotherelectronicandcomputingdevices(notshoWn).
Thesystembus508representsanynumberofseveraltypesofbusstructures,includingamemorybusormemorycontroller,aperipheralbus,anacceleratedgraphicsport,andaprocessororlocalbususinganyofavarietyofbusarchitectures.
Thesystemmemory509includescomputer-readablemediaintheformofvolatilememory,suchasrandomaccessmemory(RAM),and/ornon-volatilememory,suchasreadonlymemory(ROM).
Abasicinput/outputsystem(BIOS)isstoredinROM.
RAMtypicallycontainsdataand/orprogrammodulesthatareimmediatelyaccessibletoand/orpresentlyoperatedonbyoneormoreoftheprocessors507.
Massstoragedevices504maybecoupledtothecomputingdevice501orincorporatedintothecomputingdevicebycouplingtothebuss.
Suchmassstoragedevices504mayincludeamagneticdiskdriveWhichreadsfromandWritestoaremovable,nonvolatilemagneticdisk(e.
g.
,a"oppydisk")505,oranopticaldiskdrivethatreadsfromand/orWritestoaremovable,non-volatileopticaldisksuchasaCDROMorthelike506.
Computerreadablemedia505,506typicallyembodycomputerreadableinstructions,datastructures,programmodulesandthelikesuppliedonoppydisks,CDs,portablememorysticksandthelike.
Anynumberofprogrammodulescanbestoredontheharddisk510,Massstoragedevice504,ROMand/orRAM509,includingbyWayofexample,anoperatingsystem,oneormoreapplicationprograms,otherprogrammodules,andprogramdata.
Eachofsuchoperatingsystem,applicationprograms,otherprogrammodulesandprogramdata(orsomecombinationthereof)mayincludeanembodimentofthesystemsandmethodsdescribedherein.
Adisplaydevice502canbeconnectedtothesystembus508viaaninterface,suchasavideoadapter511.
AusercaninterfaceWithcomputingdevice702viaanynumberofdifferentinputdevices503suchasakeyboard,pointingdevice,joystick,gamepad,serialport,and/orthelike.
Theseandotherinputdevicesareconnectedtotheprocessors507viainput/outputinterfaces512thatarecoupledtothesystembus508,butmaybeconnectedbyotherinterfaceandbusstructures,suchasaparallelport,gameport,and/orauniversalserialbus(USB).
Computingdevice500canoperateinanetWorkedenvironmentusingconnectionstooneormoreremotecomputersthroughoneormorelocalareanetWorks(LANs),WideareanetWorks(WANs)andthelike.
Thecomputingdevice501isconnectedtoanetWork514viaanetWorkadapter513oralternativelybyamodem,DSL,ISDNinterfaceorthelike.
ThoseskilledintheartWillrealizethatstoragedevicesutilizedtostoreprograminstructionscanbedistributedacrossanetWork.
ForexamplearemotecomputermaystoreanexampleoftheprocessdescribedassoftWare.
AlocalorterminalcomputermayaccesstheremotecomputeranddoWnloadapartorallofthesoftWaretoruntheprogram.
AlternativelythelocalcomputermaydoWnloadpiecesofthesoftWareasneeded,ordistributivelyprocessbyexecutingsomesoftWareinstructionsatthelocalterminalandsomeattheremotecomputer(orcomputernetWork).
ThoseskilledintheartWillalsorealizethatbyutilizingconventionaltechUS7,644,074B2niquesknowntothoseskilledintheartthatall,oraportionofthesoftwareinstructionsmaybecarriedoutbyadedicatedcircuit,suchasaDSP,programmablelogicarray,orthelike.
Theinventionclaimedis:1.
Amethodofsearchingbydocumenttypecomprising:receivingasearchqueryhavingatopictypeofthesearchquery,thetopictypecomprisingatypeoftopictoWhichthesearchqueryisdirected;rankingrstmatchingdocumentsaccordingtorelevancetothesearchquerytoformarankedrelevancelist,Wherein10therankingisperformedbyapplyingthesearchquerytoarelevancymodelthatWastrainedWithtrainingdatacomprisingtrainingdataelements,atrainingdataelementcomprisingapreviously-madequery,adocumentsatisfyingthepreviously-madequery,andcorrespondinginformationindicatingrelevancyofthedocumenttothepreviously-madequery,Wheretherelevancymodelisastatisticalmodelthatrankstherstmatchingdocuments;forthesamesearchquery,rankingsecondmatchingdocumentsaccordingtotopictypetoformarankedtypelistinWhichthesecondmatchingdocumentsarerankedaccordingtorespectiveprobabilitiesthattheirrespectivetopictypesmatchthetopictypeofthesearchquery,andWhereintherankingisperformedusingatypingmodelthatWastrainedWithtrainingdatacomprisingtrainingdataelements,atrainingdataelementcomprisingadocumentandcorrespondingtypinginformationindicatingatopictypeofthedocument,Wherethetypingmodelisastatisticalmodelthatranksthesecondmatchingdocumentsaccordingtotheprobabilitiesoftheirtopictypesmatchingthesearchquery'stopictype;andusinglinearinterpolationtointerpolatetherankedrelevancelistandtherankedtypelisttoformalistofdocumentsfromtherelevancelistandtherankedtypelisttype,thelistofdocumentsbeingrankedbasedonbothrelevanceandtype,thelistofdocumentsincludingdocumentsfromtherstmatchingdocumentsanddocumentsfromthesecondmatchingdocuments.
2.
Themethodofsearchingbydocumenttypeofclaim1inWhichrankingdocumentsaccordingtorelevancetoformarankedrelevancelistisperformedbyadocumentrelevancesearch.
3.
Themethodofsearchingbydocumenttypeofclaim2inWhichthedocumentrelevancesearchisOkapi.
2025303540104.
Themethodsearchingbydocumenttypeofclaim1inWhichrankingdocumentsaccordingtotypetoformarankedtypelistisperformedbyaclassier.
5.
Themethodsearchingbydocumenttypeofclaim4inWhichtheclassierislogisticregression.
6.
Oneormorecomputer-readablestoragemediastoringinformationtoenableamachinetoperformaprocess,theprocesscomprising:receivingasearchqueryhavingatopictypeofthesearchquery,thetopictypecomprisingatypeoftopictoWhichthesearchqueryisdirected;rankingrstmatchingdocumentsaccordingtorelevancetothesearchquerytoformarankedrelevancelist,WhereintherankingisperformedbyapplyingthesearchquerytoarelevancymodelthatWastrainedWithtrainingdatacomprisingtrainingdataelements,atrainingdataelementcomprisingapreviously-madequery,adocumentsatisfyingthepreviously-madequery,andcorrespondinginformationindicatingrelevancyofthedocumenttothepreviously-madequery,Wheretherelevancymodelisastatisticalmodelthatrankstherstmatchingdocuments;forthesamesearchquery,rankingsecondmatchingdocumentsaccordingtotopictypetoformarankedtypelistinWhichthesecondmatchingdocumentsarerankedaccordingtorespectiveprobabilitiesthattheirrespectivetopictypesmatchthetopictypeofthesearchquery,andWhereintherankingisperformedusingatypingmodelthatWastrainedWithtrainingdatacomprisingtrainingdataelements,atrainingdataelementcomprisingadocumentandcorrespondingtypinginformationindicatingatopictypeofthedocument,Wherethetypingmodelisastatisticalmodelthatranksthesecondmatchingdocumentsaccordingtotheprobabilitiesoftheirtopictypesmatchingthesearchquery'stopictype;andusinglinearinterpolationtointerpolatetherankedrelevancelistandtherankedtypelisttoformalistofdocumentsfromtherelevancelistandtherankedtypelisttype,thelistofdocumentsbeingrankedbasedonbothrelevanceandtype,thelistofdocumentsincludingdocumentsfromtherstmatchingdocumentsanddocumentsfromthesecondmatchingdocuments.
US007644074B2(10)PatentN0.
:(45)DateofPatent:US7,644,074B2Jan.
5,2010(54)(75)(73)(21)(22)(65)(51)(52)SEARCHBYDOCUMENTTYPEANDRELEVANCEInventors:YunboCa0,Beijing(CN);HangLi,Beijing(CN);JunXu,Tianjin(CN)(58)FieldofClassicationSearch707/100Seeapplicationleforcompletesearchhistory.
(56)ReferencesCitedU.
S.
PATENTDOCUMENTS___2005/0182783A1*8/2005Vadaieta1.
.
.
707/102Ass1gnee:MicrosoftCorporation,Redmond,WA2005/0246314A1>ilDisk''\5ProgramMLIGSJ/ProcessingRAMProgramUnit'IIIIII|I|=EEROMtL50]HOInterfaces505'-506HODevicepegrpicg'al503504500US7,644,074B21SEARCHBYDOCUMENTTYPEANDRELEVANCEBACKGROUNDThisdescriptionrelatesgenerallytocomputeraidedsearchingandmorespecicallytosearchingforinstructiondocuments.
Peopleoftenfaceunfamiliartasks,andthustheyneedappropriateinstructionsforconductingthem.
MuchefforthasbeenmadetocopeWiththeproblem.
Includingbooksforpopular'hoW-to'questions.
ManyonlineservicesforansWeringhoW-toquestionsarealsoavailableWhichcanmaintainalargecollectionofinstructiondocumentsandprovideasearchserviceonthecollection.
However,noneofthemtypicallycancoverallofthehoWtoquestionsindailylife.
Thus,itcouldbehelpfultohaveasystemthathelpsautomaticallyretrieve'instructions'(i.
e.
,documentsoftaskguides)ontheWeb(eitherInternetorintranet).
SUMMARYThefolloWingpresentsasimpliedsummaryofthedisclosureinordertoprovideabasicunderstandingtothereader.
ThissummaryisnotanextensiveovervieWofthedisclosureanditdoesnotidentifykey/criticalelementsoftheinventionordelineatethescopeoftheinvention.
Itssolepurposeistopresentsomeconceptsdisclosedhereininasimpliedformasapreludetothemoredetaileddescriptionthatispresentedlater.
ThepresentexampleprovidesaWaytosearchformanualsorotherdocumentsbycombiningarelevancemodelandatypemodel.
Trainingdataisprovidedtoeachmodelandthemodelisthenappliedtoarstpluralityofdocuments.
TWocollectionsofdocumentsresult.
Arstcollectionrankedbytype,andasecondcollectionrankedbyrelevance.
Throughalinearinterpolationthedocumentsarecombinedtoproduceasecondpluralityofdocumentsrankedbyrelevanceandtype.
ManyoftheattendantfeaturesWillbemorereadilyappreciatedasthesamebecomesbetterunderstoodbyreferencetothefolloWingdetaileddescriptionconsideredinconnectionWiththeaccompanyingdraWings.
DESCRIPTIONOFTHEDRAWINGSThepresentdescriptionWillbebetterunderstoodfromthefolloWingdetaileddescriptionreadinlightoftheaccompanyingdraWings,Wherein:FIG.
1shoWstWoexamplesofWebdocumentsthatmaybefoundinaconventionalsearch.
FIG.
2shoWstWoexemplaryinstructiondocumentsfoundastheresultofaconventionalsearchpertainingtothequery'hoWtocompileAmaya'.
FIG.
3shoWsexamplesofdocumentsthatmightbefoundasaresultofasearch.
FIG.
4isaHowdiagramshoWingmanualssearchbyusingarelevancemodelandatypemodel.
FIG.
5illustratesanexemplarycomputingenvironment500inWhichthemanualssearchbyusingarelevancemodelandatypemodeldescribedinthisapplication,maybeimplemented.
LikereferencenumeralsareusedtodesignatelikepartsintheaccompanyingdraWings.
202530354045505560652DETAILEDDESCRIPTIONThedetaileddescriptionprovidedbeloWinconnectionWiththeappendeddraWingsisintendedasadescriptionofthepresentexamplesandisnotintendedtorepresenttheonlyformsinWhichthepresentexamplemaybeconstructedorutiliZed.
Thedescriptionsetsforththefunctionsoftheexampleandthesequenceofstepsforconstructingandoperatingtheexample.
HoWever,thesameorequivalentfunctionsandsequencesmaybeaccomplishedbydifferentexamples.
TheexamplesbeloWdescribeamanualssearchbyusingarelevancemodelandatypemodel.
Althoughthepresentexamplesaredescribedandillustratedhereinasbeingimplementedinaninstructionmanualsearchsystem,thesystemdescribedisprovidedasanexampleandnotalimitation.
AsthoseskilledintheartWillappreciate,thepresentexamplesaresuitableforapplicationinavarietyofdifferenttypesofsearchsystems.
Traditionalinformationretrievaltypicallyaimsatndingrelevantdocuments.
HoWever,relevantdocumentsfoundinthismannerarenotnecessarilyinstructiondocuments,i.
e.
,ansWerstohoW-toquestions.
Thus,anaiveapplicationofthetraditionalinformationretrievalmaynotproducethedesiredinstructions.
InthefolloWingexample,investigationofquestionansWeringinaneWsettingisprovidedbyamethodcalled"manualssearch".
Morespecically,givenahoW-toquery,alldocumentsmaybeautomaticallyretrievedandrankedWhicharerelevanttothequeryandWhicharealsolikelytobeaninstructiondocument.
Inparticularthetrainingtypemanualisinterpreted,orseen,asaclassicationproblem.
Andthemethodoffusingscoresfromthetypemodelandtherelevancemodelmaybedonebylinearlyinterpolatingthescores.
TheexamplesbeloWprovideamanualssearchprocesstypicallyutiliZingarelevancemodelandatypemodel.
Specically,Whengivena'hoW-to'typeofquery(e.
g.
,'hoWtocreatealink'),documentsareretrievedandrankedthemaccordingtoboththelikelihoodofbeinganinstructiondocument(adocumentcontainingdescriptionabouthoWtoperformatask)andtherelevancetothequery.
Traditionaldocumentretrievaltypicallyonlyconsiderstherelevanceofdocumentstoqueries.
ThemethodofperformingthetaskmayincludeWhatmaybereferredtohereas'relevancemodel'and'typemodel'.
Withtherelevancemodel,itisdeterminedWhetherornotadocumentisrelevanttoaquery.
Withthetypemodel,itisdeterminedWhetherornotadocumentisaninstructiondocument.
OkapiandLogisticRegressionmaybeemployedastherelevancemodelandthetypemodel,respectively.
AmethodforcombiningtheusesofthetWomodelsbasedonlinearinterpolationisalsoproposed.
Intheexampleprovidedthemethodisdescribedintermsofamanualssearch.
Morespecically,givenahoW-toquery,documentsWhicharerelevanttothequeryandWhicharelikelytobeinstructiondocumentsareretrievedandranked.
Themanualssearchisbasedonarelevancemodelandatypemodel.
OkapimaybeemployedastherelevancemodelandLogisticRegressionasthetypemodel,respectively.
Amethodbasedonalinearinterpolationtechniqueisalsoproposedtofusetheoutputoftherelevancemodelandthetypemodel.
TheinstantmanualssearchtypicallyperformsWellonbotharticialdatasetsandrealdatasets.
ForhoW-toqueries,goodinstructiondocumentsareoftenrankedhigherusingtheexemplaryapproachthanthebaselinemethodofeithersolelyusingOkapiorsolelyusingLogisticRegression.
TheproposedapproachtypicallyperformsWellondifferentdomains.
US7,644,074B23Theexampleprovidedofamethodofmanualssearchmaybebasedonarelevancemodelandatypemodel.
InparticularOkapimaybeemployedastherelevancemodelandLogisticRegressionasthetypemodel,respectively.
Okapiisasystemfordocumentretrievalbasedonaprobabilisticmodel.
Itretrievesandranksdocumentsaccordingtotherelevanceofdocumentstoqueries.
Okapioritsequivalentmaybeemployedintheexampleprovided.
OkapiisdescribedmorefullybyS.
E.
Robertson,S.
Walker,M.
M.
Beaulieu,M.
Gatford,andA.
Payne.
OkapiatTREC-4.
InD.
K.
Harman,editor,TheFourthTextRetrievalConference(TREC-4),pages73-96,Gaithersburg,Md.
,1996.
NationalInstituteofStandardsandTechnology,SpecialPublication500-236.
LogisticRegressionisaprobabilisticclassicationmodelmorefullydescribedinT.
Hastie,R.
Tibshirani,andJ.
Friedman.
TheElementsofStatisticalLearning.
Springer,N.
Y.
,2001.
IncontrasttootherclassicationmodelssuchasSupportVectorMachine(SVM),LogisticRegressiontypicallyoutputsprobabilityvaluesratherthanscoresinclassication.
AmethodbasedonalinearinterpolationtechniqueisalsoutiliZedtofusetheoutputoftherelevancemodelandthetypemodel.
Amanualssearchmaybemorehelpfulthanaconventionalsearchthattendstoreturnagreaterrangeofresults,manyofWhicharenotinstructions.
Inperformingamanualssearchaqueryistypicallyreceivedrst.
ThequeryisusuallyahoW-toquestion,e.
g.
,'hoWtocreatealink'.
Nextusingconventionalmethodsautomaticretrievalofalloftherelevantandlikelyinstructiondocumentsisperformed.
Next,thedocumentsmayberankedaccordingtothedegreeoflikelihoodofbeinganinstructiondocumentandthedegreeofrelevancetothequery.
ManualssearchtypicallyneedstoassurethattheretrieveddocumentsarerelevanttothequeriesasWell.
HoWever,incontrast,manualssearchmayalsoneedtoassurethattheretrieveddocumentsareinstructiondocuments.
Table1shoWspossiblesetsofdocumentsthatmaybesearchedfor.
FromTable1,Aisthesetthatistypicallydesiredinmanualssearch.
Cisthesetthatisrelevantbutnon-instructionandthusshouldbelteredout.
TABLE1TWovieWsofdocumentsRelevantIrrelevantInstructionABNon-instructionCDFIG.
1shoWstWoexamplesofWebdocumentsthatmaybefoundinaconventionalsearch.
Therstdocument101isnotaninstructiondocumentandtheseconddocument102isaninstructiondocument.
Thus,ifthequeryis'hoWtocreatealink',thentheseconddocument102Wouldbepreferredbyusers.
HoWever,ifonlyrelevanceisconsidered,thentherstdocument101Willlikelyberankedhigher,becauseitWouldtypicallyappeartobemorerelevanttothequery.
QuestionansWeringmaybeidealforaccessinginformationoninstructions,ifrealiZed,becauseitsgoalistoprovideasinglecombinedansWer.
OnecansimplygetallthenecessaryinformationbyreadingthecombinedansWer.
HoWever,generationofsuchacombinedansWermaybeverychallengingorevenimpossibleforcurrentsystems.
First,mostansWerstoahoWtoqueryconsistofstep-by-stepguidesastheexampleshoWnintheseconddocumentinFIG.
2.
Deletions,insertions,orre-orderingsmadeinanypartofthedocumentmayconfuseormisguidetypicalsearches.
Second,differentinstruction202530354045505560654documentsmayhavedifferentassumptionsandsettings,evenforthesametopic.
Thusitmaynotbeappropriatetocombinetheinstructionsbasedondifferentassumptionsandsettings.
FIG.
2shoWstWoexemplaryinstructiondocumentsfoundastheresultofaconventionalsearchpertainingtothequery'hoWtocompileAmaya'.
HoWever,theyprovideinstructionsfordifferentsettings.
Onedocument201providesinstructions'WithAutoconf'settings.
Theotherdocument202providesinstructionsWithWindoWs'settings.
Therefore,areasonableapproachWouldbetoshoWuserstheinstructiondocumentsseparately.
AsseenabovejudgingWhetheradocumentisarelevantinstructiondocument,andthuscanbeusedasanansWertoahoW-toqueryinanobjectiveWaymaybehard.
HoWever,Wecanstillproviderelativelyobjectiveguidelinesforthejudgment.
TheobjectiveguidelinesWillbetermedthespecicationinthisfolloWingdescription.
Thespecicationmaybeusedextensivelyfordevelopmentandevaluationofthemanualssearchprocess.
AspreviouslyshoWninTable1,thespecicationcanbedesignedfromtWovieWpoints.
Forthenotionofrelevance,specicationmaybedenedinasimilarfashionasthatintraditionalinformationretrieval.
Indoingsothenotionofinstructionisclariedrst.
FIG.
3shoWsexamplesofdocuments301302303thatmightbefoundasaresultofasearch.
First,aninstructiondocumentisadocumentcreatedforansWeringahoW-toquery.
Morespecically,byreadingthedocument,onecanunderstandhoWtoperformthetaskofthehoW-toquery.
Second,intheexampleprovided,aninstructiondocumentisassumednottobeadocumentcontaininginstructionsforanumberofdifferenttasks.
Forexample,therstdocumentinFIG.
4isnotregardedasaninstructiondocument.
Third,intheexampleprovided,aninstructiondocumentisassumednottobeadocumentthatonlyconsistspartlyofinstructions.
Forexample,theseconddocument302isnotvieWedasaninstructiondocument,becauseasectionofitisabouthoW-to.
Ascanbeseenfromtheabovediscussionsomeinstructiondocumentsmaycontainstep-by-stepguides(cf.
,theseconddocumentinFIG.
2);Whileotherinstructiondocumentsmayjustconsistofseveralsentences(e.
g.
,thelastdocumentinFIG.
4).
Thecriteriausedabovemaybequantiedforuseinamanualssearch.
Withthespecicationdenedabove,fourlabelssimilartothoseinTable1areprovided.
Forthepurposesofmanualssearch,hoWever,thereshouldbenodifferencebetWeenthelabelsCandD.
Thus,WecombineCandDtogethertoC-D.
Inmanualssearch,givenaqueryqandadocumentd,oneofthethreelabelsbeloWcanbeassigned:A:documentdisrelevanttoqandisaninstructiondocumentB:documentdisirrelevanttoqbutisaninstructiondocumentC-D:documentdisofnouseFIG.
4isaHowdiagramshoWingmanualssearchbyusingarelevancemodel401andatypemodel402.
Intheexampleprovidedofmanualssearchbyusingarelevancemodelandatypemodeltheinputmaybeaquery403andacollectionofdocuments404.
Thedocumentsmayhaveresultedfromaconventionalsearch,ormaysimplybeacollectionofdocumentstobeexamined.
TheexemplaryapproachtomanualssearchincludestWosteps.
First,arepresentationtorelevancetoaqueryandalikelihoodofbeinganinstructiondocumentisformedWithtWosub-models,WhichWecalla'relevancemodel'401anda'typemodel'402,respectively.
Intherelevancemodel,itisjudgedWhetherornotadocumentintheinputisrelevanttothequery407.
Inthetypemodel,itisjudgedWhetherornotadocumentintheinputisaninstrucUS7,644,074B25tiondocument408.
Next,alinearinterpolationtechniquemaybeusedtocombinethescoresoutputfromthetWosub-models405.
Thedocumentsarethenrankedindescendingorderoftheircombinedscores406.
AsshoWntrainingdatamaybesuppliedingeneraltoatrainingrelevancemodel.
However,trainingdataisnotneededWiththeexemplaryOkapiBM25modelorothertypesofrelevancemodelsthatmaybeutilizedinplaceofOkapiBM25.
Intheexampleprovidedtrainingdatamayalsobesuppliedtothetypemodel,hoWeveritisanticipatedthatinsomeapplicationstrainingdatamaynotbeneeded.
RelevanceModel(Okapi)GivenahoW-toqueryandadocument,therelevancemodelndsarelevancescore.
Inmanualssearch,foragivenquery,alistofpairsusingtherelevancemodeltogeneratetherelevancescorearecreated.
InthepresentexampletheOkapiBM25relevancescoremaybeemployedastherelevancemodel.
Forindexingthetitleandthebodyofadocumentareindexedinseparateelds.
Foreacheld,theOkapiBM25Weightingschemeisusedtocalculateascore.
Thenthescoresofthetitleeldandthebodyeldarecombinedlinearly,andthecombinedscoreisvieWedastherelevance-score.
TypeModel(LogisticRegression)Givenadocument,thetypemodeloutputsatypescore.
ThatmeansthatWeassumethatthetypemodelisindependentfromqueries.
Inmanualssearch,Wecreatealistofpairsusingthetypemodel.
Wetakeastatisticalmachinelearningapproachtoconstructingatypemodel.
Morespecically,givenatrainingdatasetD:{xi,yi}l",WeconstructamodelPr(y|x)thatcanminimizetheerrorinpredictingofygivenx(generalizationerror).
Herexi6Xandyl-e{l,—lxrepresentsadocumentandyrepresentsWhetherornotadocumentisaninstructiondocument.
WhenappliedtoaneWdocumentx,themodelpredictsthecorrespondingyandoutputsthescoreoftheprediction.
Inthisexample,WeadopttheLogisticRegressionModel.
LogisticRegressionTheLogisticRegressionModelsatises:Where[3representsthecoefcientsofalinearcombinationfunctionand[30istheintercept.
TheLogisticRegressionModelisusuallyestimatedbyusingMaximumLikelihood.
TheLogisticRegressionModelassignsaprobabilitytoaninstance(inourcaseadocument)probabilityaccordingtothefolloWingequation.
Wecalculatethetype-scoreofadocumentaccordingto:Pr(y=1IX)typeiscore:logm(3)202530354045505560656FeaturesTheLogisticRegressionModelutilizesbinaryorrealvaluedfeaturesasdescribedbeloW.
Mostfeaturesarecreatedtocharacterizetitle,rstheadingandrstsentenceofdocuments.
AlthoughthoseskilledintheartWillrealizethatinalternativeexamplesfeaturesarenotlimitedtocharacterizationsoftitlesheadingsentencesandthelike.
TitleisthetextenclosedbytheHTMLtag''and''.
HeadingisthetextenclosedbytheHTMLtag''and''.
Firstheadingreferstotherstnon-emptyheadingofaHTMLdocument.
FirstsentenceistherstsentenceappearinginthebodyofaHTMLdocument.
'HoWTo'WhetherornotthetitleofadocumentcontainstheWordsof'hoWto','hoWto'or'hoW-to'isanimportantindicator.
Thisisrepresentedusingabinaryfeature.
TherearesimilarfeaturesWithregardtotherstheadingandtherstsentenceofadocument.
ThoseskilledintheartWillrealizethatinalternativeexamplesofknoWledgeextractionotherWordsorphrasesofinterestmaybeidentiedandusedasimportantindicators.
'DoingSomething'Theappearanceofthesufx'ing'intherstWordofthetitleisanotherindicatorofaninstructiondocument.
Sometimespeopleusethetemplateof'doingsomething'insteadof'hoWtodosomething'forthetitleofaninstructiondocument.
Thevalueofthefeatureisbinary,too.
Similarfeatureshavealsobeendenedfortherstheadingandtherstsentence.
ThoseskilledintheartWillrealizethatotherWordsorWordfragmentsfromthetitlemaybeuseddependinguponthespecicapplicationofsearchbyusingarelevancemodelandatypemodel.
TextLengthAlsodenedisthefolloWingreal-valuedfeature:log(length(title)+l)(4)Wherelength(title)denotesthenumberofWordsinthetitle.
AdocumentWithashorttitle(egaone-Wordtitle)tendstobeanon-instructiondocument.
Similarfeatureshavealsobeendenedfortherstheadingandtherstsentence.
IdenticalExpressionsIfthetextsinanytWoofthethreeparts:title,rstheadingandrstsentenceareidentical,thenthisfeatureis1.
OtherWise,itis0.
Aninstructiondocumentusuallyrepeatsitstopicinthesethreeplaces.
BagofWordsAlsorelieduponare'bag-of-Words'features.
ThemethodcollectshighfrequencyWordsinthetitlesofthedocumentsintrainingdataandcreateabagofthekeyWords.
SomekeyWordsplaypositiveroles(e.
g.
,'troubleshoot','Wizards')andsomenegativeones(e.
g.
,'contact').
IfthetitleofadocumentcontainsoneofthekeyWords,thenthecorrespondingfeatureWillbe1,otherWise0.
Similarfeatureshavebeendenedfortherstheadingandtherstsentence.
CombinationofRelevanceandTypeModelsAranking_scoremaybecalculatedbylinearlyinterpolatingtherelevance_scoreandtype_scoreastheEquation(5).
rankingscore:7vtypeiscore+(l—7t)-relevanceiscore(5)Here,7e[0,l]isaWeightusedtobalancethecontributionoftherelevancemodelandthetypemodel.
AsWillbeexplainedlateritistypicallybettertohave7:0.
5Inmanualssearch,documentsareretrievedandrankedindescendingorderoftheranking_score.
US7,644,074B27Inprinciple,givenaqueryandadocumentcollection,onecancalculatetherankingscoreofeachofthedocumentsWithrespecttothequery.
Inanimplementationofthemethod,thetop100documentsrankedbytherelevancemodel(Okapi)arerstcollected.
Nextrankingscoresarecalculatedonlyforthetop100documents.
InthisWay,amanualssearchmaybeconductedveryefciently.
GeneralizationManualssearchmaybeformalizedinamoregeneralframeworkcalled'typedsearch'.
Intypedsearch,documentsareretrievedandrankednotonlyonthebasisofrelevancetothequery,butalsothelikelihoodofbeingthedesiredtype.
Givenaqueryqandadocumentd,WecalculatetherankingscoreofthepairusingEquation(6):Pr(r,llq,d)=Pr(rlq,d)-Pr(lld)(6)Whererandtdenoterelevanceandtype,respectively.
Bothrandtarebinaryvariables.
Inmanualsearch,forexample,tmeansthatadocumentisaninstructiondocument.
Intheequation,Wemakeanassumptionthatrandtgivenaqanddareindependent.
Therearemany'types'thatcanbeconsideredsuchasdenition,letter,andhomepage,forexample.
Inmanualssearch,onecandenetherelevancescoreandthetypescoreaslogoddsofPr(r|q,d)andPr(t|d),respectively(cf.
,Equation(3)).
ThisjustiesWhyWemakeuseofequalWeightinthelinearcombinationinEquation(5).
Kraajjetal.
haveproposedusingLanguageModelinthetaskofhome/namedpagending.
TheyemployamodelasfolloWs,Whichassignsascoretoapagedgivenaqueryq:TherstmodelontherighthandsideofEquation(7),correspondstothetypemodelinEquation(6)andthesecondmodelcorrespondstotherelevancemodel.
Therefore,homepagendingcanbevieWedasaspecializationoftypedsearch.
ForfurtherinformationonusingaLanguageModelseeW.
Kraajj,T.
WesterveldandD.
Hiemstra.
TheImporlanceofPriorProbabililiesforEnlryPageSearch.
InProc.
ofthe25thannualinternationalACMSIGIRconferenceonresearchanddevelopmentininformationretrieval,2002.
ThecontentsofWhichareincorporatedinthispatentapplicationintheirentirety,ConclusionsInmanualssearchthedocumentshavebeenrankedbycombiningarelevancemodelandatypemodel.
OkapiandLogisticRegressionhavebeenusedastherelevancemodelandthetypemodel,respectively.
FinalrankingscoresarethenobtainedbylinearlyinterpolatingthescoresfromthetWomodels.
TheproposedmethodmaybegeneralizedinageneralframeWorkcalledtypedsearch.
FIG.
5illustratesanexemplarycomputingenvironment500inWhichthemanualssearchbyusingarelevancemodelandatypemodeldescribedinthisapplication,maybeimplemented.
Exemplarycomputingenvironment500isonlyoneexampleofacomputingsystemandisnotintendedtolimittheexamplesdescribedinthisapplicationtothisparticularcomputingenvironment.
Forexamplethecomputingenvironment500canbeimplementedWithnumerousothergeneralpurposeorspecialpurposecomputingsystemcongurations.
ExamplesofWellknoWncomputingsystems,mayinclude,butarenotlimitedto,personalcomputers,hand-heldorlaptopdevices,microprocessor-basedsystems,multiprocessorsystems,settopboxes,gamingconsoles,consumerelectronics,cellulartelephones,PDAs,andthelike.
2030354045505560658Thecomputer500includesageneral-purposecomputingsystemintheformofacomputingdevice501.
Thecomponentsofcomputingdevice501canincludeoneormoreprocessors(includingCPUs,GPUs,microprocessorsandthelike)507,asystemmemory509,andasystembus508thatcouplesthevarioussystemcomponents.
Processor507processesvariouscomputerexecutableinstructions,includingthoseto**tocontroltheoperationofcomputingdevice501andtocommunicateWithotherelectronicandcomputingdevices(notshoWn).
Thesystembus508representsanynumberofseveraltypesofbusstructures,includingamemorybusormemorycontroller,aperipheralbus,anacceleratedgraphicsport,andaprocessororlocalbususinganyofavarietyofbusarchitectures.
Thesystemmemory509includescomputer-readablemediaintheformofvolatilememory,suchasrandomaccessmemory(RAM),and/ornon-volatilememory,suchasreadonlymemory(ROM).
Abasicinput/outputsystem(BIOS)isstoredinROM.
RAMtypicallycontainsdataand/orprogrammodulesthatareimmediatelyaccessibletoand/orpresentlyoperatedonbyoneormoreoftheprocessors507.
Massstoragedevices504maybecoupledtothecomputingdevice501orincorporatedintothecomputingdevicebycouplingtothebuss.
Suchmassstoragedevices504mayincludeamagneticdiskdriveWhichreadsfromandWritestoaremovable,nonvolatilemagneticdisk(e.
g.
,a"oppydisk")505,oranopticaldiskdrivethatreadsfromand/orWritestoaremovable,non-volatileopticaldisksuchasaCDROMorthelike506.
Computerreadablemedia505,506typicallyembodycomputerreadableinstructions,datastructures,programmodulesandthelikesuppliedonoppydisks,CDs,portablememorysticksandthelike.
Anynumberofprogrammodulescanbestoredontheharddisk510,Massstoragedevice504,ROMand/orRAM509,includingbyWayofexample,anoperatingsystem,oneormoreapplicationprograms,otherprogrammodules,andprogramdata.
Eachofsuchoperatingsystem,applicationprograms,otherprogrammodulesandprogramdata(orsomecombinationthereof)mayincludeanembodimentofthesystemsandmethodsdescribedherein.
Adisplaydevice502canbeconnectedtothesystembus508viaaninterface,suchasavideoadapter511.
AusercaninterfaceWithcomputingdevice702viaanynumberofdifferentinputdevices503suchasakeyboard,pointingdevice,joystick,gamepad,serialport,and/orthelike.
Theseandotherinputdevicesareconnectedtotheprocessors507viainput/outputinterfaces512thatarecoupledtothesystembus508,butmaybeconnectedbyotherinterfaceandbusstructures,suchasaparallelport,gameport,and/orauniversalserialbus(USB).
Computingdevice500canoperateinanetWorkedenvironmentusingconnectionstooneormoreremotecomputersthroughoneormorelocalareanetWorks(LANs),WideareanetWorks(WANs)andthelike.
Thecomputingdevice501isconnectedtoanetWork514viaanetWorkadapter513oralternativelybyamodem,DSL,ISDNinterfaceorthelike.
ThoseskilledintheartWillrealizethatstoragedevicesutilizedtostoreprograminstructionscanbedistributedacrossanetWork.
ForexamplearemotecomputermaystoreanexampleoftheprocessdescribedassoftWare.
AlocalorterminalcomputermayaccesstheremotecomputeranddoWnloadapartorallofthesoftWaretoruntheprogram.
AlternativelythelocalcomputermaydoWnloadpiecesofthesoftWareasneeded,ordistributivelyprocessbyexecutingsomesoftWareinstructionsatthelocalterminalandsomeattheremotecomputer(orcomputernetWork).
ThoseskilledintheartWillalsorealizethatbyutilizingconventionaltechUS7,644,074B2niquesknowntothoseskilledintheartthatall,oraportionofthesoftwareinstructionsmaybecarriedoutbyadedicatedcircuit,suchasaDSP,programmablelogicarray,orthelike.
Theinventionclaimedis:1.
Amethodofsearchingbydocumenttypecomprising:receivingasearchqueryhavingatopictypeofthesearchquery,thetopictypecomprisingatypeoftopictoWhichthesearchqueryisdirected;rankingrstmatchingdocumentsaccordingtorelevancetothesearchquerytoformarankedrelevancelist,Wherein10therankingisperformedbyapplyingthesearchquerytoarelevancymodelthatWastrainedWithtrainingdatacomprisingtrainingdataelements,atrainingdataelementcomprisingapreviously-madequery,adocumentsatisfyingthepreviously-madequery,andcorrespondinginformationindicatingrelevancyofthedocumenttothepreviously-madequery,Wheretherelevancymodelisastatisticalmodelthatrankstherstmatchingdocuments;forthesamesearchquery,rankingsecondmatchingdocumentsaccordingtotopictypetoformarankedtypelistinWhichthesecondmatchingdocumentsarerankedaccordingtorespectiveprobabilitiesthattheirrespectivetopictypesmatchthetopictypeofthesearchquery,andWhereintherankingisperformedusingatypingmodelthatWastrainedWithtrainingdatacomprisingtrainingdataelements,atrainingdataelementcomprisingadocumentandcorrespondingtypinginformationindicatingatopictypeofthedocument,Wherethetypingmodelisastatisticalmodelthatranksthesecondmatchingdocumentsaccordingtotheprobabilitiesoftheirtopictypesmatchingthesearchquery'stopictype;andusinglinearinterpolationtointerpolatetherankedrelevancelistandtherankedtypelisttoformalistofdocumentsfromtherelevancelistandtherankedtypelisttype,thelistofdocumentsbeingrankedbasedonbothrelevanceandtype,thelistofdocumentsincludingdocumentsfromtherstmatchingdocumentsanddocumentsfromthesecondmatchingdocuments.
2.
Themethodofsearchingbydocumenttypeofclaim1inWhichrankingdocumentsaccordingtorelevancetoformarankedrelevancelistisperformedbyadocumentrelevancesearch.
3.
Themethodofsearchingbydocumenttypeofclaim2inWhichthedocumentrelevancesearchisOkapi.
2025303540104.
Themethodsearchingbydocumenttypeofclaim1inWhichrankingdocumentsaccordingtotypetoformarankedtypelistisperformedbyaclassier.
5.
Themethodsearchingbydocumenttypeofclaim4inWhichtheclassierislogisticregression.
6.
Oneormorecomputer-readablestoragemediastoringinformationtoenableamachinetoperformaprocess,theprocesscomprising:receivingasearchqueryhavingatopictypeofthesearchquery,thetopictypecomprisingatypeoftopictoWhichthesearchqueryisdirected;rankingrstmatchingdocumentsaccordingtorelevancetothesearchquerytoformarankedrelevancelist,WhereintherankingisperformedbyapplyingthesearchquerytoarelevancymodelthatWastrainedWithtrainingdatacomprisingtrainingdataelements,atrainingdataelementcomprisingapreviously-madequery,adocumentsatisfyingthepreviously-madequery,andcorrespondinginformationindicatingrelevancyofthedocumenttothepreviously-madequery,Wheretherelevancymodelisastatisticalmodelthatrankstherstmatchingdocuments;forthesamesearchquery,rankingsecondmatchingdocumentsaccordingtotopictypetoformarankedtypelistinWhichthesecondmatchingdocumentsarerankedaccordingtorespectiveprobabilitiesthattheirrespectivetopictypesmatchthetopictypeofthesearchquery,andWhereintherankingisperformedusingatypingmodelthatWastrainedWithtrainingdatacomprisingtrainingdataelements,atrainingdataelementcomprisingadocumentandcorrespondingtypinginformationindicatingatopictypeofthedocument,Wherethetypingmodelisastatisticalmodelthatranksthesecondmatchingdocumentsaccordingtotheprobabilitiesoftheirtopictypesmatchingthesearchquery'stopictype;andusinglinearinterpolationtointerpolatetherankedrelevancelistandtherankedtypelisttoformalistofdocumentsfromtherelevancelistandtherankedtypelisttype,thelistofdocumentsbeingrankedbasedonbothrelevanceandtype,thelistofdocumentsincludingdocumentsfromtherstmatchingdocumentsanddocumentsfromthesecondmatchingdocuments.
轻云互联22元/月，美国硅谷、圣何塞CN2GIA云服务器，香港沙田cn2建站vps仅25元/月
轻云互联怎么样?轻云互联，广州轻云网络科技有限公司旗下品牌，2018年5月成立以来，轻云互联以性价比的价格一直为提供个人,中大小型企业/团队云上解决方案。本次轻云互联送上的是美国圣何塞cn2 vps(免费50G集群防御)及香港沙田cn2 vps(免费10G集群防御)促销活动，促销产品均为cn2直连中国大陆线路、采用kvm虚拟技术架构及静态内存。目前，轻云互联推出美国硅谷、圣何塞CN2GIA云服务器...
VirMach（8元/月）KVM VPS，北美、欧洲
VirMach，成立于2014年的美国IDC商家，知名的低价便宜VPS销售商，支持支付宝、微信、PayPal等方式付款购买，主打美国、欧洲暑假中心产品，拥有包括洛杉矶、西雅图、圣何塞、凤凰城在内的11个数据中心可以选择，可以自由搭配1Gbps、2Gbps、10Gbps带宽端口，有Voxility DDoS高防IP可以选择（500Gbps以上的防御能力），并且支持在控制面板付费切换机房和更换IP（带...
弘速云（28元/月）香港葵湾2核2G10M云服务器
弘速云怎么样?弘速云是创建于2021年的品牌，运营该品牌的公司HOSU LIMITED(中文名称弘速科技有限公司)公司成立于2021年国内公司注册于2019年。HOSU LIMITED主要从事出售香港vps、美国VPS、香港独立服务器、香港站群服务器等，目前在售VPS线路有CN2+BGP、CN2 GIA，该公司旗下产品均采用KVM虚拟化架构。可联系商家代安装iso系统，目前推出全场vps新开7折，...
644为你推荐
-
域名空间代理域名空间服务商哪个好啊？找了一天都没确定哪个好？免费云主机免费云主机哪家好？海外服务器租用国外服务器租用与国内服务器租用有哪些区别com域名空间域名和空间是什么意思免费虚拟主机申请求免费可以申请的域名和虚拟主机com域名注册com域名是永久注册的吗台湾主机台湾的电脑硬件比韩国，日本，美国强？海外域名求国外域名商列表免费网站空间免费网站空间哪个好免费网站空间申请如何申请到免费的网站空间