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.
TmhHost香港三网CN2 GIA月付45元起,美国CN2 GIA高防VPS季付99元起
TmhHost是一家国内正规公司，具备ISP\ICP等资质，主营国内外云服务器及独立服务器租用业务，目前，商家新上香港三网CN2 GIA线路VPS及国内镇江BGP高防云主机，其中香港三网CN2 GIA线路最低每月45元起；同时对美国洛杉矶CN2 GIA线路高防及普通VPS进行优惠促销，优惠后美国洛杉矶Cera机房CN2 GIA线路高防VPS季付99元起。香港CN2 GIA安畅机房，三网回程CN2 ...
Contabo美国独立日促销,独立服7月€3.99/月
Contabo自4月份在新加坡增设数据中心以后，这才短短的过去不到3个月，现在同时新增了美国纽约和西雅图数据中心。可见Contabo加速了全球布局，目前可选的数据中心包括：德国本土、美国东部（纽约）、美国西部（西雅图）、美国中部（圣路易斯）和亚洲的新加坡数据中心。为了庆祝美国独立日和新增数据中心，自7月4日开始，购买美国地区的VPS、VDS和独立服务器均免设置费。Contabo是德国的老牌服务商，...
青云互联19元/月，美国洛杉矶CN2GIA/香港安畅CN2云服务器低至;日本云主机
青云互联怎么样?青云互联美国洛杉矶cn2GIA云服务器低至19元/月起;香港安畅cn2云服务器低至19元/月起;日本cn2云主机低至35元/月起!青云互联是一家成立于2020年的主机服务商,致力于为用户提供高性价比稳定快速的主机托管服务。青云互联本站之前已经更新过很多相关文章介绍了，青云互联的机房有香港和洛杉矶，都有CN2 GIA线路、洛杉矶带高防，商家承诺试用7天，打死全额退款点击进入：青云互联...
644为你推荐
-
免费虚拟空间找个免费的虚拟主机空间，20M以上的免费虚拟主机空间请问哪里有：免费一级域名申请,免费虚拟主机，免费空间vps汽车的VPS是什么，和GPS有什么区别国外主机空间可以购买国外主机（空间一样吗？）来做私服吗？云服务器租用谁知道租用服务器、云主机去哪里租？服务器租用费用价格是多少呀虚拟空间哪个好国内哪个空间商（虚拟主机）最好国外网站空间怎么样把网站空间放到国外去?重庆网站空间重庆建网站选择哪家比较好，还有域名空间等，虚拟主机管理系统大家都用的是什么虚拟主机管理系统？分享一下大连虚拟主机找个大连企业建站公司，大家给推荐一下吧。