機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘相關(guān)現(xiàn)代信息檢索lecture19websearch

第19講Web搜索WebSearch12011/12/01提綱2上一講回顧

互聯(lián)網(wǎng)發(fā)展趨勢(shì)

互聯(lián)網(wǎng)廣告

重復(fù)檢測(cè)提綱3上一講回顧

互聯(lián)網(wǎng)發(fā)展趨勢(shì)

互聯(lián)網(wǎng)廣告

重復(fù)檢測(cè)4SVD分解的例子C=UΣVT:所有的四個(gè)矩陣45將空間維度降為2實(shí)際上，我們只需將矩陣Σ中相應(yīng)的維度置為0即可。此時(shí)，相當(dāng)于矩陣U和VT

的相應(yīng)維度被忽略，然后計(jì)算C2=UΣ2VT.56為什么新的低維空間更好？6在原始空間中，d2和d3的相似度為0；但是在新空間下，

d2和d3的相似度為：0.52*0.28+0.36*0.16+0.72*0.36+0.12*0.20+-0.39*-0.08≈0.527本講內(nèi)容互聯(lián)網(wǎng)發(fā)展趨勢(shì)分析互聯(lián)網(wǎng)廣告重復(fù)檢測(cè)7提綱8上一講回顧

互聯(lián)網(wǎng)發(fā)展趨勢(shì)

互聯(lián)網(wǎng)廣告

重復(fù)檢測(cè)9Web搜索系統(tǒng)組成910搜索是Web上使用最多的應(yīng)用之一1011沒(méi)有搜索引擎，Web甚至無(wú)法運(yùn)轉(zhuǎn)沒(méi)有搜索，很難找到所需的內(nèi)容→沒(méi)有搜索，在Web上創(chuàng)建內(nèi)容也就缺了動(dòng)機(jī)如果沒(méi)人看為什么要發(fā)布內(nèi)容？如果沒(méi)有任何回報(bào)為什么要發(fā)布內(nèi)容？Web上必須要有人買單服務(wù)器、Web基礎(chǔ)設(shè)施、內(nèi)容創(chuàng)建過(guò)程等需要費(fèi)用支持這些費(fèi)用的大部分都是通過(guò)搜索廣告支付可以說(shuō)，搜索為Web買單1112興趣聚合(Interestaggregation)Web的特點(diǎn)：具有相同興趣的人，即使所處地理位置分散，也可以通過(guò)Web找到對(duì)方患有血友病的小學(xué)生們將R5R5語(yǔ)言翻譯成可便攜C語(yǔ)言的人們(開(kāi)源項(xiàng)目和社區(qū))搜索引擎是實(shí)現(xiàn)興趣聚合的關(guān)鍵事物1213

WebIRvs.一般的IR在Web上，搜索不僅僅是一個(gè)好的特點(diǎn)搜索是Web的關(guān)鍵事物:......籌資、內(nèi)容創(chuàng)建、興趣聚合等等

→參考搜索廣告Web是一個(gè)充滿噪聲數(shù)據(jù)且組織失調(diào)的集合體

→大量的重復(fù)需要檢測(cè)用戶可以無(wú)控制和無(wú)限制地發(fā)布內(nèi)容→大量作弊內(nèi)容需要檢測(cè)Web規(guī)模非常大

→需要知道Web的規(guī)模大小13提綱14

上一講回顧

互聯(lián)網(wǎng)發(fā)展趨勢(shì)

互聯(lián)網(wǎng)廣告

重復(fù)檢測(cè)15第一代搜索廣告:Goto(1996)競(jìng)價(jià)排名1516第一代搜索廣告:Goto(1996)16BuddyBlake為此搜索投出最高價(jià)($0.38)只要某個(gè)人點(diǎn)擊了該鏈接，BuddyBlake就要付$0.38的費(fèi)用給Goto公司搜索結(jié)果按照投標(biāo)價(jià)格的順序排序–Goto可以獲得最大的收益不區(qū)分廣告還是文檔，僅僅是一個(gè)結(jié)果列表！廣告預(yù)售，坦誠(chéng)公開(kāi)，沒(méi)有相關(guān)度排序...但是Goto并不假裝存在相關(guān)度17第二代搜索廣告:Google(2000/2001)17嚴(yán)格區(qū)分搜索結(jié)果和搜索廣告18兩個(gè)列表結(jié)果:web網(wǎng)頁(yè)(左圖)及廣告(右圖)18SogoTrade出現(xiàn)在搜索結(jié)果中SogoTrade出現(xiàn)在廣告中搜索引擎是不是把廣告商的結(jié)果放在非廣告商的結(jié)果之前？所有的主流搜索引擎都否認(rèn)這一點(diǎn)19廣告是否會(huì)影響編輯的內(nèi)容？

在報(bào)紙、電視上存在類似問(wèn)題報(bào)紙一般不會(huì)刊登針對(duì)其主要廣告商的嚴(yán)厲指責(zé)性質(zhì)的文章在報(bào)紙和TV上，廣告和編輯內(nèi)容之間的界限往往變得很模糊現(xiàn)在還不清楚搜索引擎廣告是否和上面一樣1920廣告在右部如何排序？2021如何對(duì)廣告排序？廣告商對(duì)關(guān)鍵詞競(jìng)標(biāo)–拍賣方式拍賣系統(tǒng)公開(kāi)，任何人都可以參與關(guān)鍵詞競(jìng)標(biāo)廣告商僅在用戶點(diǎn)擊廣告商才真正付費(fèi)拍賣機(jī)制如何確定某條廣告的排序以及該廣告的支付價(jià)格？基本思路是次高價(jià)拍賣(secondpriceauction)原則搜索引擎中最重要的研究領(lǐng)域之一計(jì)算廣告學(xué)對(duì)每條廣告壓榨出一分錢也就意味著為搜索引擎公司帶來(lái)上億的額外收益2122如何對(duì)廣告排序？簡(jiǎn)單的方法:按照類似Goto的方式，即按照投標(biāo)價(jià)格排序不好的方法:可能會(huì)被濫用例如：query[doesmyhusbandcheat?]→有關(guān)離婚律師的廣告我們并不像得到相關(guān)性上無(wú)關(guān)的廣告替代方法：

按照投標(biāo)價(jià)格和相關(guān)性排序相關(guān)度度量的關(guān)鍵指標(biāo)：點(diǎn)擊率(clickthroughrate)clickthroughrate=CTR=clicksperimpressions結(jié)果：無(wú)關(guān)的廣告將得到很低的排名即使在短期時(shí)間內(nèi)降低了搜索引擎的收益希望：如果用戶能通過(guò)系統(tǒng)獲得有價(jià)值的信息，那么系統(tǒng)的總體接受程度和整體收益將最大化其他排序因子：位置、一天內(nèi)的時(shí)間、著陸頁(yè)(landingpage)的質(zhì)量和裝載速度最主要的排序因子：查詢2223GoogleAdsWords的例子2324Google次高競(jìng)標(biāo)價(jià)格拍賣機(jī)制

bid:每個(gè)廣告商為每次點(diǎn)擊給出的最大投標(biāo)價(jià)格CTR:點(diǎn)擊率，即一旦被顯示后被點(diǎn)擊的比率。CTR是一種相關(guān)性度量指標(biāo)。adrank:bid×CTR:這種做法可以在(i)廣告商愿意支付的價(jià)錢(ii)廣告的相關(guān)度高低之間進(jìn)行平衡。rank:拍賣中的排名paid:廣告商的次高競(jìng)標(biāo)價(jià)格2425Google次高競(jìng)標(biāo)價(jià)格拍賣機(jī)制次高競(jìng)標(biāo)價(jià)格拍賣：

廣告商支付其維持在拍賣中排名所必須的價(jià)錢(加上一分錢)(用它的下一名計(jì)算其支付價(jià)格)price1×CTR1=bid2×CTR2(使得排名rank1=rank2)price1=bid2×CTR2/CTR1p1=bid2×CTR2/CTR1=3.00×0.03/0.06=1.50p2=bid3×CTR3/CTR2=1.00×0.08/0.03=2.67p3=bid4×CTR4/CTR3=4.00×0.01/0.08=0.502526具有高投標(biāo)價(jià)格的關(guān)鍵詞參考$69.1 mesotheliomatreatmentoptions$65.9 personalinjurylawyermichigan$62.6 studentloansconsolidation$61.4 caraccidentattorneylosangeles$59.4 onlinecarinsurancequotes$59.4 arizonaduilawyer$46.4 asbestoscancer$40.1 homeequitylineofcredit$39.8 lifeinsurancequotes$39.2 refinancing$38.7 equitylineofcredit$38.0 lasikeyesurgerynewyorkcity$37.0 2ndmortgage$35.9 freecarinsurancequote2627搜索廣告:三贏？每次用戶點(diǎn)擊廣告，搜索引擎公司將會(huì)獲得收益用戶只會(huì)點(diǎn)擊其感興趣的廣告搜索引擎會(huì)對(duì)誤導(dǎo)性和不相關(guān)的廣告進(jìn)行懲罰于是，用戶在點(diǎn)擊廣告后往往會(huì)感到滿意廣告商通過(guò)廣告能夠在物有所值的情況下找到新的客戶2728

課堂練習(xí)為什么和TV、報(bào)紙和電臺(tái)相比，Web搜索對(duì)廣告商更有吸引力？廣告商會(huì)為所有一切買單，那么它們會(huì)受到欺騙嗎？這對(duì)用戶來(lái)說(shuō)究竟是好消息還是壞消息？當(dāng)然，不論如何做，這都會(huì)危害搜索引擎2829

并非三贏:關(guān)鍵詞套現(xiàn)(Keywordarbitrage)比如從Google買一個(gè)關(guān)鍵詞然后將流量導(dǎo)向一個(gè)第三方頁(yè)面，該頁(yè)面對(duì)應(yīng)機(jī)構(gòu)付的錢將比你付給Google的多得多比如，重定向到一個(gè)滿是廣告的頁(yè)面該頁(yè)面對(duì)于搜索用戶來(lái)說(shuō)基本沒(méi)意義廣告作弊者一直在鉆營(yíng)想招搜索引擎必須要要花時(shí)間對(duì)付他們2930并非三贏:商標(biāo)侵權(quán)例子:geico(美國(guó)政府雇員保險(xiǎn)公司，是美國(guó)第四大私人客戶汽車保險(xiǎn)公司)2005年的部分時(shí)間內(nèi):搜索詞項(xiàng)“geico”在Google上可以買到Geico在美國(guó)控告Google侵權(quán)LouisVuitton(LV)在歐洲控告Google侵權(quán)參考complaint.html如果采用商標(biāo)做關(guān)鍵詞，那么用戶可能被誤導(dǎo)到一個(gè)頁(yè)面，該頁(yè)面實(shí)際和用戶期望購(gòu)買的品牌產(chǎn)品無(wú)關(guān)30提綱31上一講回顧

互聯(lián)網(wǎng)發(fā)展趨勢(shì)

互聯(lián)網(wǎng)廣告

重復(fù)檢測(cè)32

重復(fù)檢測(cè)Web上充斥重復(fù)內(nèi)容相對(duì)其它文檔集合，Web上的重復(fù)內(nèi)容更多完全重復(fù)(Exactduplicate)易剔除，比如采用哈希/指紋的方法近似重復(fù)(Near-duplicate)Web上存在大量近似重復(fù)很難剔除對(duì)用戶而言，如果搜索結(jié)果中存在不少幾乎相同的頁(yè)面，那么體驗(yàn)非常不好邊緣相關(guān)度(Marginalrelevance)為0：如果一篇高度相關(guān)的文檔出現(xiàn)在另一篇高度近似的文檔之后，那么該文檔變得不相關(guān)(冗余)必須要去除這些近似重復(fù)3233

近似重復(fù)的例子3334

課堂思考題如何去掉Web上的近似重復(fù)頁(yè)面呢？3435近似重復(fù)的檢測(cè)采用編輯距離指標(biāo)計(jì)算頁(yè)面之間的相似度需要說(shuō)明的是，我們希望檢測(cè)那些“語(yǔ)法”(syntactic)上而不是“語(yǔ)義”(semantic)上相似的頁(yè)面頁(yè)面的語(yǔ)義相似度(即內(nèi)容語(yǔ)義之間的相似度)非常難以計(jì)算也就是說(shuō)，我們并不考慮那些內(nèi)容意義上相似但是表達(dá)方式不同的近似重復(fù)引入一個(gè)相似度閾值θ來(lái)判定“兩個(gè)頁(yè)面之間是否近似重復(fù)”比如，如果兩篇文檔的相似度

>

閾值θ=80%，那么認(rèn)為兩篇文檔近似重復(fù)3536將每篇文檔表示成一個(gè)shingle集合每個(gè)shingle是一個(gè)基于詞語(yǔ)的n-gram使用shingle來(lái)計(jì)算文檔之間的語(yǔ)法相似度比如，對(duì)于n=3，那么文檔“aroseisaroseisarose”就可以表示成shingle的集合：{a-rose-is,rose-is-a,is-a-rose}我們可以通過(guò)指紋(fingerprinting)算法將shingle映射到1..2m(例如m=64)之間接下來(lái)我們用sk

來(lái)代表某個(gè)shingle映射到1..2m之間的一個(gè)數(shù)兩個(gè)文檔的相似度定義為它們的shingle集合的Jaccard距離3637Jaccard距離計(jì)算回顧一個(gè)常用的計(jì)算兩個(gè)集合重合度的方法令

A

和

B

分別表示兩個(gè)集合Jaccard距離:

JACCARD(A,A)=1JACCARD(A,B)=0ifA∩B=0并不要求A和B

的大小一樣Jaccard距離取值在[0,1]之間3738Jaccard距離計(jì)算的例子3篇文檔：

d1:“JackLondontraveledtoOakland”d2:“JackLondontraveledtothecityofOakland”d3:“JacktraveledfromOaklandtoLondon”基于2-gram的shingle表示，可以計(jì)算文檔之間的Jaccard距離如下：J(d1,d2)=3/8=0.375J(d1,d3)=0注意：Jaccard距離對(duì)差異十分敏感3839將文檔表示成梗概(sketch)每篇文檔的shingle的個(gè)數(shù)非常大為提高效率，接下來(lái)我們使用文檔的梗概來(lái)表示文檔，它由文檔的shingle集合中精巧挑選出的子集構(gòu)成比如，梗概中shingle的數(shù)目為

n=200......通過(guò)一系列置換π1...π200來(lái)定義每個(gè)置換

πi

都是1..2m上的隨機(jī)置換文檔d的梗概定義為：<mins∈d

π1(s),mins∈d

π2(s),...,mins∈d

π200(s)>(一個(gè)200維的數(shù)字向量)3940置換和最小值：例子文檔1:{sk}文檔2:{sk}使用mins∈d1π(s)=mins∈d2

π(s)作為文檔

d1

和

d2是否近似重復(fù)的測(cè)試條件？

該例子中置換π表明:d1≈d24041計(jì)算梗概之間的Jaccard距離(1)現(xiàn)在每篇文檔都變成了一個(gè)n=200維的數(shù)字向量該向量比高維空間下的shingle容易處理得多如何計(jì)算Jaccard距離?4142計(jì)算梗概之間的Jaccard距離(2)如何計(jì)算？令U

為d1和d2的并集，I為它們的交集對(duì)于U而言就存在|U|!個(gè)置換對(duì)于

s′∈I,有多少置換

π

會(huì)使得

argmins∈d1

π(s)=s′=argmins∈d2

π(s)?答案是:(|U|?1)!對(duì)于I的每個(gè)s，存在著(|U|?1)!個(gè)不同的置換集合?于是總共有|I|(|U|?1)!個(gè)置換能夠保證

argmins∈d1

π(s)=argmins∈d2

π(s)為真因此，使得mins∈d1π(s)=mins∈d2π(s)為真的置換比例為：4243Jaccard距離估計(jì)因此，成功的置換比例就等于Jaccard距離置換

π成功當(dāng)且僅當(dāng)

mins∈d1π(s)=mins∈d2π(s)隨機(jī)選取一個(gè)置換，當(dāng)置換成功是輸出1，否則輸出0，該過(guò)程是一個(gè)貝努利試驗(yàn)過(guò)程成功概率的估計(jì)：在

n

次貝努利試驗(yàn)中成功比率(n=200)我們使用的梗概基于置換的隨機(jī)選擇因此，為了計(jì)算Jaccard距離，統(tǒng)計(jì)<d1,d2>上的成功置換個(gè)數(shù)k，然后除以n=200.k/n=k/200就是

J(d1,d2)的估計(jì)值4344

實(shí)現(xiàn)使用哈希函數(shù)來(lái)實(shí)現(xiàn)高效的置換: hi:{1..2m}→{1..2m}以任意順序掃描兩個(gè)集合并集中的所有shinglesk對(duì)每個(gè)哈希函數(shù)

hi

及文檔d1,d2,...:在某個(gè)固定存儲(chǔ)位置中保留當(dāng)前的最小值如果hi(sk)小于當(dāng)前的最小