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.
bgpto：日本独立服务器6.5折($120起)，新加坡独立服务器7.5折（$93起）
bgp.to在对日本东京的独立服务器进行6.5折终身优惠促销，低至$120/月；对新加坡独立服务器进行7.5折终身优惠促销，低至$93/月。所有服务器都是直连国内，速度上面相比欧洲、美国有明显的优势，特别适合建站、远程办公等多种用途。官方网站：https://www.bgp.to/dedicated.html主打日本（东京、大阪）、新加坡、香港（CN）、洛杉矶（US）的服务器业务！日本服务器CPU...
cloudcone：特价便宜VPS补货通知贴,SAS或SSD低价有磁盘阵列，SAS或SSD raid10 硬盘
cloudcone经常性有特价促销VPS放出来，每次的数量都是相当有限的，为了方便、及时帮助大家，主机测评这里就做这个cloudcone特价VPS补货专题吧，以后每次放货我会在这里更新一下日期，方便大家秒杀！官方网站：https://cloudcone.com/预交费模式，需要充值之后方可使用，系统自动扣费！信用卡、PayPal、支付宝，均可付款购买！为什么说cloudcone值得买？cloudc...
香港云服务器最便宜价格是多少钱一个月、一年?
香港云服务器最便宜价格是多少钱一个月/一年?无论香港云服务器推出什么类型的配置和活动，价格都会一直吸引我们，那么就来说说香港最便宜的云服务器类型和香港最低的云服务器价格吧。香港云服务器最便宜最低价的价格是多少?香港云服务器只是服务器中最受欢迎的产品。香港云服务器有多种配置类型，如1核1G、2核2G、2核4G、8到16核32G等。这些配置可以满足大多数用户的需求，无论是电商站、视频还是游戏、小说等。...
644为你推荐
-
空间租用网站空间申请是免费的吗？还有就是使用租用空间，这种便宜空间好使吗？虚拟主机评测网求推荐一些适合个人博客网站的虚拟主机的服务商1g虚拟主机打算买个1G的虚拟主机，用来做什么好？合肥虚拟主机虚拟主机哪里买好一些？论坛虚拟主机我要做个论坛，是用虚拟主机呢？还是用空间？除论坛外还有好及个单页，还带数据库。中文域名中文域名是怎么回事？解析域名网站上的域名解析是什么意思？已备案域名什么是微信已备案域名域名买卖域名买卖能赚钱吗？查询域名怎样来查看域名的解析地址