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.
Nocser：马来西亚独立服务器促销$60.00/月
Nocser刚刚在WHT发布了几款促销服务器，Intel Xeon X3430，8GB内存，1TB HDD，30M不限流量，月付$60.00。Nocser是一家注册于马来西亚的主机商，主要经营虚拟主机、VPS和马来西亚独立服务器业务，数据中心位于马来西亚AIMS机房，线路方面，AIMS到国内电信一般，绕日本NTT；联通和移动比较友好，联通走新加坡，移动走香港，延迟都在100左右。促销马来西亚服务器...
VoLLcloud：超便宜香港CMI大带宽vps-三网CMI直连-年付四免服务-低至4刀/月-奈飞
vollcloud LLC创立于2020年，是一家以互联网基础业务服务为主的 技术型企业，运营全球数据中心业务。致力于全球服务器租用、托管及云计算、DDOS安 全防护、数据实时存储、 高防服务器加速、域名、智能高防服务器、网络安全服务解决方案等领域的智 能化、规范化的体验服务。所有购买年付产品免费更换香港原生IP(支持解锁奈飞),商家承诺，支持3天内无条件退款(原路退回)!点击进入：vollclo...
tmhhost：暑假快乐，全高端线路，VPS直接8折，200G高防，美国gia日本软银韩国cn2香港cn2大带宽
tmhhost为2021年暑假开启了全场大促销，全部都是高端线路的VPS，速度快有保障。美国洛杉矶CN2 GIA+200G高防、洛杉矶三网CN2 GIA、洛杉矶CERA机房CN2 GIA，日本软银（100M带宽）、香港BGP直连200M带宽、香港三网CN2 GIA、韩国双向CN2。本次活动结束于8月31日。官方网站：https://www.tmhhost.com8折优惠码：TMH-SUMMER日本...
644为你推荐
-
国际域名国际域名和国内域名有什么不同，什么叫顶级域名？虚拟主机购买虚拟主机需要购买吗？我想自己做个网站，只买了域名了，请问还需要怎么做呢？深圳网站空间深圳网站设计 哪家好一些？免费网站空间申请哪个网站可以申请免费的网页空间韩国虚拟主机韩国虚拟主机好还是香港的好m3型虚拟主机建网站，M型虚拟主机和G型虚拟主机，选哪种好？申请域名如何申请域名？花生壳域名花生壳域名的使用org域名.org域名和.com哪个域名好？域名估价域名评估，看看域名的价值多少钱