全書(shū)教學(xué)課件：web搜索

Web搜索

第1章導(dǎo)論Web搜索的定義Web搜索的發(fā)展背景Web搜索的挑戰(zhàn)性Web搜索的科學(xué)價(jià)值Web搜索的研究狀況本課的內(nèi)容Web搜索的定義Web搜索(WebSearch):是指在以環(huán)球網(wǎng)WorldWideWeb為典型代表的網(wǎng)絡(luò)上檢索、過(guò)濾和推薦信息的理論、方法、技術(shù)、系統(tǒng)和服務(wù)檢索(retrieval)是由用戶提出查詢需求，系統(tǒng)根據(jù)這個(gè)需求對(duì)Web信息進(jìn)行查詢并給出結(jié)果過(guò)濾(filtering)是系統(tǒng)根據(jù)預(yù)先設(shè)定的條件，對(duì)Web中與該條件相符的信息進(jìn)行提取、隔離或封堵推薦(recommendation)是系統(tǒng)將用戶需要的重要信息從大量的一般信息中提取出來(lái)，并主動(dòng)推薦給用戶三者的聯(lián)系與區(qū)別，與傳統(tǒng)信息檢索的區(qū)別Web搜索的發(fā)展背景網(wǎng)絡(luò)與數(shù)字內(nèi)容技術(shù)的發(fā)展光纖骨干傳輸網(wǎng)絡(luò)、寬帶無(wú)線接入網(wǎng)絡(luò)相繼建成數(shù)字內(nèi)容采集制作技術(shù)的日益成熟大容量存儲(chǔ)器的廉價(jià)化網(wǎng)絡(luò)數(shù)字內(nèi)容:

時(shí)事新聞、數(shù)字音像、科學(xué)文獻(xiàn)、遠(yuǎn)程教育動(dòng)漫游戲、金融信息、政府公告、網(wǎng)絡(luò)論壇網(wǎng)絡(luò)博客、音視頻播客、彩信彩鈴、微博……對(duì)Web搜索的需求Web信息的海量化反而使人們的信息查詢變得更加困難人們永遠(yuǎn)懷疑得到的東西是不是最好的Web中非法、有害和垃圾信息的大量傳播嚴(yán)重污染了Web信息環(huán)境，干擾和妨礙了人們的信息利用在Web信息極其豐富的條件下，如何為用戶提供有用信息是一個(gè)非常重要的問(wèn)題Web搜索的挑戰(zhàn)性數(shù)據(jù)海量:巨大尺度的數(shù)據(jù)處理對(duì)算法產(chǎn)生全新要求數(shù)據(jù)稀疏:Web不齊全、不完整和不一致媒體多樣:文本、圖像、視頻、音頻、二進(jìn)制程序代碼、二進(jìn)制數(shù)值等，每種形式又分為眾多的子類大量并發(fā)請(qǐng)求:面向大眾，服務(wù)請(qǐng)求的并發(fā)性非常高數(shù)據(jù)特征演進(jìn):Web數(shù)據(jù)總是動(dòng)態(tài)變化的，這種變化包括主題、媒體、數(shù)據(jù)量等多方面的變化主觀客觀交叉:Web上的信息是客觀存在，但這種客觀存在是受大眾的主觀需求影響的Web搜索的科學(xué)價(jià)值Web搜索所研究的是一個(gè)嶄新的科學(xué)問(wèn)題—如何在無(wú)邊的動(dòng)態(tài)的Web空間中尋找最符合用戶需求的信息。這個(gè)問(wèn)題不僅在尺度上空前巨大，而且約束條件非常不確定Web搜索既要考慮信息的客觀性，又要考慮信息的主觀性Web搜索強(qiáng)有力地帶動(dòng)了相關(guān)學(xué)科，特別是智能學(xué)科的發(fā)展Web搜索的研究狀況國(guó)家863計(jì)劃、國(guó)家973計(jì)劃以及國(guó)家自然科學(xué)基金都在積極開(kāi)展有關(guān)的研究SIGIR、SIGKDD、TREC、TDT、MUC、ACE等國(guó)際會(huì)議和評(píng)測(cè)活動(dòng)十分活躍理論研究方面取得了長(zhǎng)足的進(jìn)步文本搜索、圖像檢索、音頻檢索、社會(huì)網(wǎng)絡(luò)搜索TREC在系統(tǒng)模型研究方面發(fā)揮引導(dǎo)作用Ad-hoc、Novelty、HARD、QA等總體上仍處于發(fā)展的初級(jí)階段本課的內(nèi)容(1/4)第2章:文本檢索

Web信息采集、文本組織索引文本內(nèi)容表示、用戶查詢方法相關(guān)文本排序、文本聚類文本分類、特征選擇與變換第3章:圖像檢索圖像的文本自動(dòng)標(biāo)注、物體識(shí)別文字識(shí)別、人臉檢測(cè)與識(shí)別

視頻的鏡頭切分、視頻摘要本課的內(nèi)容(2/4)第4章:音頻檢索聲學(xué)特征提取、基于HMM的語(yǔ)音識(shí)別語(yǔ)音關(guān)鍵詞發(fā)現(xiàn)及檢測(cè)音頻的聲學(xué)模型、音頻的語(yǔ)義模型聲學(xué)模型與語(yǔ)義模型的聯(lián)系音樂(lè)檢索模型本課的內(nèi)容(2/4)第5章:信息過(guò)濾信息過(guò)濾系統(tǒng)中的分類器選擇學(xué)習(xí)和優(yōu)化問(wèn)題垃圾信息過(guò)濾系統(tǒng)話題檢測(cè)與追蹤(TDT)系統(tǒng)本課的內(nèi)容(3/4)第6章:信息推薦基本關(guān)聯(lián)規(guī)則挖掘算法可信關(guān)聯(lián)規(guī)則及其挖掘算法超團(tuán)模式快速挖掘算法協(xié)同過(guò)濾推薦的基本算法基于局部偏好的協(xié)同過(guò)濾推薦算法基于個(gè)性化主動(dòng)學(xué)習(xí)的協(xié)同過(guò)濾面向排序的協(xié)同過(guò)濾

本課的內(nèi)容(4/4)第7章:發(fā)展前沿基于文檔的專家檢索對(duì)象檢索及信息抽取基于Web的對(duì)象檢索博客檢索

TREC中的博客觀點(diǎn)檢索文本情感分析

教材郭軍:Web搜索，高等教育出版社，2009年8月購(gòu)書(shū)網(wǎng)址:

:購(gòu)書(shū)熱線/p>

Web搜索

第2章文本檢索Web信息采集文本的保存與索引檢索模型網(wǎng)頁(yè)排序查詢重構(gòu)文本聚類文本分類特征選擇特征變換引言文本是最基本、最高級(jí)的信息媒體文本檢索是Web搜索的起點(diǎn)文本檢索所涉及的問(wèn)題Web信息的采集與組織文本的表示用戶查詢方法相關(guān)文檔排序文本聚類文本分類Web信息采集Crawler/Spider:利用hyperlink自動(dòng)獲取網(wǎng)頁(yè)的URL利用HTTP進(jìn)行網(wǎng)絡(luò)編程自動(dòng)下載網(wǎng)頁(yè)Crawler的基本原理網(wǎng)頁(yè)采集過(guò)程是一個(gè)從WWW的某網(wǎng)頁(yè)出發(fā)不斷向前漫游的過(guò)程漫游的方向和路線是隨機(jī)的為了將隨機(jī)漫游變成有序的向外擴(kuò)展，必須對(duì)其進(jìn)行有效地控制Crawler的工作進(jìn)程Crawler的工作效率多線程Crawler分布式Crawler:通過(guò)分散在不同地點(diǎn)的服務(wù)器實(shí)現(xiàn)Crawler的難題前沿URL的選擇廣度優(yōu)先/深度優(yōu)先?優(yōu)質(zhì)網(wǎng)頁(yè)優(yōu)先？無(wú)效URL問(wèn)題同一網(wǎng)頁(yè)的多重訪問(wèn)問(wèn)題網(wǎng)頁(yè)的再訪問(wèn)周期問(wèn)題文本的預(yù)處理與保存預(yù)處理網(wǎng)頁(yè)去重:基于消息摘要/鏈接結(jié)構(gòu)網(wǎng)頁(yè)解析:HTML/XML文檔的解析，取出其中的元數(shù)據(jù)、超鏈接、標(biāo)題和文本內(nèi)容文本的保存文本通常以壓縮的形式保存網(wǎng)頁(yè)一般長(zhǎng)度為10KB，壓縮后為2-4KB通用文件系統(tǒng)的存儲(chǔ)塊尺寸為4-8KB網(wǎng)頁(yè)存儲(chǔ)通常采用專門(mén)開(kāi)發(fā)的文件系統(tǒng)大型商用搜索引擎需要在全球建立多個(gè)鏡像的文件系統(tǒng)骨干服務(wù)器文本的索引(1/2)建立索引本質(zhì)上就是建立標(biāo)記來(lái)指示內(nèi)容的位置Web搜索通常情況下是全文搜索，即對(duì)網(wǎng)頁(yè)中包含的所有詞匯都建立索引倒排文件(invertedfile)詞匯表(vocabulary):文本中所有不同詞匯的集合位置表(occurrences):詞匯在文本中出現(xiàn)的地址列表(postinglist)、字地址、詞地址、塊地址Heaps定律:v~O(Na

)a≈0.5Gb級(jí)文本、Mb級(jí)詞匯查詢步驟:查詢

詞匯表

位置表

文檔或段落文本的索引(2/2)倒排索引的更新—批量更新主索引+新索引(stop-pressindex)新索引(d,t,s)三元組倒排(t,d,s)對(duì)一個(gè)用戶的查詢，主索引反饋文檔集D0，新索引返回文檔集D+和D-，返回給用戶D0∪D+\D-索引壓縮文檔的標(biāo)識(shí)符壓縮:delta編碼索引詞的選取詞標(biāo)識(shí)、去停詞(stopword)、詞干化(stemming)檢索模型文本檢索的本質(zhì)問(wèn)題:用戶需求

文本集中最相關(guān)的文檔需解決的3個(gè)基本問(wèn)題用戶如何提出需求簡(jiǎn)單、簡(jiǎn)便，關(guān)鍵詞的方式相關(guān)文檔如何定義和計(jì)算語(yǔ)法層相關(guān)/語(yǔ)義層相關(guān)檢索結(jié)果如何反饋URL地址清單段落檢索QABoolean模型查詢:由關(guān)鍵詞及邏輯關(guān)系符構(gòu)成的Boolean表達(dá)式文檔:索引詞的集合查詢與文檔相關(guān)的定義:索引詞的集合是否滿足查詢Boolean表達(dá)式二元決策，無(wú)相關(guān)程度的度量人們常常不容易用Boolean表達(dá)式描述查詢用戶往往只是同時(shí)輸入多個(gè)關(guān)鍵詞，隱含地應(yīng)用“與”邏輯VSM用索引詞出現(xiàn)的絕對(duì)和相對(duì)頻度來(lái)表達(dá)文檔和查詢所有m個(gè)不同的索引詞構(gòu)成m維的特征向量文檔dj的特征向量dj=[w1j,w2j,…,wmj]查詢q的特征向量q=[w1q,w2q,…,wmq]計(jì)算q和dj之間相關(guān)性或相似性有多種方法

相關(guān)性計(jì)算余弦相似度相關(guān)系數(shù)索引詞的權(quán)重TF:IDF:TF-IDF:查詢?cè)~的權(quán)重:概率模型(1/2)給定一個(gè)用戶查詢q和一個(gè)文檔dj

，概率模型通過(guò)估計(jì)dj與q的相關(guān)的概率來(lái)判斷二者的相關(guān)性假設(shè)在所有文檔中存在一個(gè)對(duì)應(yīng)q的理想集合R，即R中的文檔都是q的相關(guān)文檔，R之外的文檔都是q的不相關(guān)文檔概率模型計(jì)算幾率比:P(djrelevanttoq)/P(djnon-relevanttoq)在概率模型中，索引詞的權(quán)重變量都是二值的，即wij

∈{0,1}，wiq

∈{0,1}概率模型(2/2)取對(duì)數(shù)后簡(jiǎn)化dj與q的相似性sim(dj,q)被定義為兩個(gè)概率的初始化

返回文檔集合V后的改進(jìn)估計(jì)Bayesian推理網(wǎng)絡(luò)模型節(jié)點(diǎn)對(duì)應(yīng)文檔、檢索詞、概念、查詢等各類實(shí)體每個(gè)節(jié)點(diǎn)都與一個(gè)隨機(jī)Boolean變量相聯(lián)系，通常采用“或”邏輯，即只要有一個(gè)父節(jié)點(diǎn)的置信邏輯為“真”，則本節(jié)點(diǎn)就為“真”網(wǎng)頁(yè)排序基于文檔與查詢的相關(guān)性的排序基于網(wǎng)頁(yè)質(zhì)量的排序通過(guò)超鏈接分析來(lái)改進(jìn)排序結(jié)果是Web文本檢索與數(shù)據(jù)庫(kù)文本檢索的一個(gè)十分重要的區(qū)別指向一個(gè)網(wǎng)頁(yè)的超鏈接的數(shù)量代表著網(wǎng)頁(yè)的流行度和質(zhì)量?jī)蓚€(gè)網(wǎng)頁(yè)包含較多的相同的鏈接或被相同的網(wǎng)頁(yè)所指向常常意味著它們之間具有某種密切的關(guān)系PageRank模擬用戶在Web上可用Markov鏈建模的“沖浪”行為假設(shè)任意節(jié)點(diǎn)u對(duì)于節(jié)點(diǎn)v都有一條有向路徑，用戶以概率分布p0隨機(jī)地從一個(gè)節(jié)點(diǎn)出發(fā)，pi為i時(shí)刻到達(dá)各節(jié)點(diǎn)的概率令Web鄰接矩陣(圖)為E，如果節(jié)點(diǎn)u和v之間存在超鏈接，則E(u,v)=1，否則為0令則p將收斂于LT的主特征向量PageRank的完善假設(shè)用戶在Web圖的每個(gè)節(jié)點(diǎn)上將進(jìn)行兩種選擇以概率q隨機(jī)瀏覽Web上的一個(gè)網(wǎng)頁(yè)以概率1-q在所有的出鏈接中以均勻概率選擇一個(gè)，繼續(xù)前進(jìn)則HITSHITS(HypertextInducedTopicSearch)與PageRank不同，是與查詢相關(guān)的網(wǎng)頁(yè)質(zhì)量評(píng)價(jià)算法收到查詢q后，系統(tǒng)返回一個(gè)網(wǎng)頁(yè)的集合RR中的任意節(jié)點(diǎn)(網(wǎng)頁(yè))指向的節(jié)點(diǎn)和指向R中任意節(jié)點(diǎn)的節(jié)點(diǎn)構(gòu)成集合X，R與X共同構(gòu)成一個(gè)基本集合V構(gòu)造圖G

=(V,E)，E為節(jié)點(diǎn)間的有向鏈接評(píng)價(jià)網(wǎng)頁(yè)的兩個(gè)測(cè)度:a(authority)和h(hub)收斂后，a等于ETE的主特征向量

h等于EET的主特征向量查詢重構(gòu)用戶提出一個(gè)適當(dāng)?shù)牟樵冋?qǐng)求往往是不容易的可將用戶的第一個(gè)查詢看作是初始的嘗試，通過(guò)對(duì)獲得的文檔的相關(guān)分析，對(duì)初始查詢進(jìn)行重構(gòu)查詢重構(gòu)的三類方法基于用戶反饋信息的的方法基于對(duì)初始反饋文檔的局部分析的方法基于對(duì)全部文檔集合的全局分析的方法用戶相關(guān)反饋先將檢索出的文檔清單提交給用戶，用戶查閱后，對(duì)相關(guān)的文檔進(jìn)行標(biāo)記設(shè)D+為用戶標(biāo)記的相關(guān)文檔的集合，D-為反饋文檔中非相關(guān)文檔的集合Rocchio公式α，β和γ都是可調(diào)參數(shù)，簡(jiǎn)單的設(shè)置是令它們都為1

在D-不好確定時(shí)，常令γ為0自動(dòng)局部分析對(duì)于一個(gè)給定的查詢q，稱檢索出來(lái)的文檔集合Dl為局部文檔集合自動(dòng)局部分析從Dl中查找查詢?cè)~的近鄰詞近鄰的測(cè)度關(guān)聯(lián)度近鄰度間接相關(guān)度

或局部語(yǔ)境分析LCA基于由名詞詞組所構(gòu)成的“概念”進(jìn)行查詢擴(kuò)展概念的定義通?；谠~典進(jìn)行步驟:1)將初始查詢檢索出的文檔分割成固定長(zhǎng)度的段落，然后按與查詢的相關(guān)性對(duì)其排序，取出前n個(gè)2)計(jì)算各段落中每個(gè)概念c與查詢q之間的相似度sim(c,q)3)將相似度最大的前m個(gè)概念加到初始查詢之中基于概念空間的全局分析尋找整個(gè)查詢的近鄰詞用文本集的所有N個(gè)文檔構(gòu)成一個(gè)概念空間，每個(gè)文檔是空間中的一個(gè)維度無(wú)論是檢索詞還是查詢，都被看作概念空間中的數(shù)據(jù)點(diǎn)，即概念，對(duì)于檢索詞ti(i=1,…,m)，ti=(wi1,…,wiN)，其中而查詢因此，q與各檢索詞的相關(guān)性

易于計(jì)算基于同義詞辭典的全局分析辭典包含若干同義詞類每個(gè)類由通過(guò)聚類算法獲得的若干檢索詞構(gòu)成采用全鏈接(completelink)的聚類算法，即類對(duì)之間的相似度被定義為所有文檔對(duì)的相似度的最小值Bottom-up的層次聚類需設(shè)置以下參數(shù)Tsim:最小類內(nèi)相似度閾值Tnod:類內(nèi)最大文檔數(shù)閾值Tidf:倒文檔頻度閾值文本聚類在文本檢索中的作用是非常廣泛和重要一直是模式識(shí)別、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域中的重點(diǎn)課題無(wú)監(jiān)督學(xué)習(xí)(Unsupervisedlearning)目的是找到數(shù)據(jù)集合中潛在(latent)的聚合結(jié)構(gòu)兩大類聚類算法區(qū)分法(discriminativemethod)生成法(generativemethod)區(qū)分式聚類的基本思想給定一個(gè)(文檔)集合D={di|i=1,…,N}其中di=(di1,…,diM)為元素di的VSM定義sim(di,dj)為元素di和dj之間的相似度聚類問(wèn)題可以定義為:將集合D劃分為k個(gè)子集D1,…Dk，使類內(nèi)的相似度總和S達(dá)到最大區(qū)分式聚類的方式區(qū)分性聚類也稱為分割聚類，由于核心操作是將集合中的元素劃分為若干子集bottom-up方式初始將每個(gè)文檔作為一類，然后對(duì)最相似的類進(jìn)行合并，直至類別數(shù)目或類內(nèi)相似度達(dá)到設(shè)定值top-down方式先將所有文檔放在一類，然后以增大類內(nèi)相似度為目標(biāo)，對(duì)類進(jìn)行分裂操作，直至類別數(shù)目或類內(nèi)相似度達(dá)到設(shè)定的閾值Bottom-up方式例Top-down方式例層次匯合聚類HAC算法1)令每個(gè)文檔d在一個(gè)單獨(dú)的組中，形成N個(gè)組mcsjzo82)令G為這N個(gè)組的集合3)while|G|>1do4)選擇u,v∈G，標(biāo)準(zhǔn)為合并它們將帶來(lái)最大的利益測(cè)度5)將u和v從G中移除6)令w=u∪v7)將w插入G8)endwhile隨著合并次數(shù)的增加，被合并類之間的相似度sim(u,v)會(huì)越來(lái)越低第4步的常用測(cè)度，S(w)的類內(nèi)相似度，w=u∪vk-means聚類算法1)初始化k個(gè)組的質(zhì)心向量2)while

還可以繼續(xù)改進(jìn)do3)

for

每個(gè)元素(文檔)d

do4)找出質(zhì)心向量與d最相似的組c5)將d調(diào)整到組c之中6)

endfor7)

for

每個(gè)組c

do8)重新計(jì)算質(zhì)心向量9)

endfor10)endwhile要點(diǎn):預(yù)先確定類別數(shù)為k質(zhì)心與元素都用向量表示軟k-means聚類硬k均值聚類:元素d要么屬于組c，要么不屬于組c，在計(jì)算質(zhì)心時(shí)，組內(nèi)所有元素都具有相同的權(quán)重軟k均值聚類:允許一個(gè)元素部分地分別屬于不同的組，但在計(jì)算組的質(zhì)心時(shí)各個(gè)元素的貢獻(xiàn)不同計(jì)算質(zhì)心的公式基于親和性消息的聚類在k均值聚類中，如果選用樣本數(shù)據(jù)為類中心，則稱為k中心法，稱被選為中心的數(shù)據(jù)為范例(exemplar)，但初始范例選取困難基于消息傳播的聚類方法[Frey07]將所有樣本看作潛在范例，數(shù)據(jù)元素通過(guò)已知的相似度被連成網(wǎng)絡(luò)，相鄰節(jié)點(diǎn)通過(guò)反復(fù)地傳遞和修改兩個(gè)消息—responsibility和availability使范例涌現(xiàn)出來(lái)基于親和性消息的聚類算法1)輸入數(shù)據(jù)元素間的相似度s(i,k)，表示k作為i的范例的適當(dāng)度2)為每個(gè)數(shù)據(jù)元素輸入偏愛(ài)度s(k,k)，該值越大k越可能為范例3)將所有可用性消息a(i,k)置為0，

a(i,k)是由k發(fā)給i的一個(gè)累積的“證據(jù)”，來(lái)證明k適合于作為i的范例4)更新依靠性消息r(i,k)，這是由i發(fā)給候選范例k的(通過(guò)與其他候選范例比較的)一個(gè)累積的“證據(jù)”，證明k適于作為i的范例5)按如下規(guī)則分別更新可用性消息a(i,k)和a(k,k)6)對(duì)每個(gè)元素i計(jì)算

，如不滿足終止條件，轉(zhuǎn)4)繼續(xù)迭代生成式聚類的基本思想每個(gè)文檔類別被看作對(duì)應(yīng)一個(gè)主題的文檔集合將文檔的產(chǎn)生看作隨機(jī)過(guò)程，每個(gè)主題類別有一個(gè)關(guān)于文檔的概率分布模型一個(gè)文檔應(yīng)該歸屬哪個(gè)類，要看哪個(gè)類別的模型產(chǎn)生該文檔的概率最大關(guān)鍵是各個(gè)類別概率模型的估計(jì)二值概率模型文檔是二值元素的向量，每個(gè)元素對(duì)應(yīng)詞表W中的一個(gè)詞t假設(shè)詞的出現(xiàn)是相互獨(dú)立的事件，并只考慮詞是否出現(xiàn)而不管出現(xiàn)的次數(shù)，則可得在概率參數(shù)集合Φ條件下文檔d生成的二值概率模型由于詞表中的詞數(shù)遠(yuǎn)遠(yuǎn)多于文檔中的詞數(shù)，所以的平均值低于0.5，使得該模型有利于短文本的生成，同時(shí)降低了實(shí)際出現(xiàn)可能性大的文檔的產(chǎn)生概率多值概率模型考慮詞在文檔中的出現(xiàn)次數(shù)假設(shè)文檔的總長(zhǎng)度L符合一個(gè)概率分布P(l)文檔的產(chǎn)生過(guò)程是一個(gè)擲|W|個(gè)面的骰子的過(guò)程，每個(gè)面對(duì)應(yīng)詞表中的一個(gè)詞產(chǎn)生長(zhǎng)度為ld的文檔的過(guò)程就等于投擲骰子ld次假設(shè)第t面出現(xiàn)了n(d,t)次，則文檔的生成概率基于概率模型的話題聚類假設(shè)要處理的文檔集合共對(duì)應(yīng)m個(gè)話題，第i類話題的產(chǎn)生概率為αi，第i類話題中詞t的產(chǎn)生概率為θi,t將m類話題文檔的所有參數(shù)表示為:獲得多類模型的關(guān)鍵步驟是通過(guò)訓(xùn)練數(shù)據(jù)將模型中的參數(shù)估計(jì)出來(lái)，著名的EM算法可用來(lái)完成這個(gè)參數(shù)估計(jì)基于MLE準(zhǔn)則的參數(shù)估計(jì)為了簡(jiǎn)化描述，假設(shè)每個(gè)類別只有一個(gè)參數(shù)μi，即用x表示要產(chǎn)生的文檔，則其生成概率設(shè)有n個(gè)iid樣本構(gòu)成訓(xùn)練集合X={x1,…,xn}，則可根據(jù)MLE準(zhǔn)則通過(guò)對(duì)以下函數(shù)最大化來(lái)估計(jì)參數(shù)ΘEM算法(E步)EM算法的思想:初始值E步/M步迭代尋優(yōu)算法在不知各個(gè)樣本的類別Y={y1,…,yn}的情況下求解先對(duì)Θ給出初始“猜想”值Θ'，令全數(shù)據(jù)似然度為X、Y和Θ'條件下L的期望值

推導(dǎo)可得由于Q是Θ的對(duì)數(shù)似然度在Y的分布上獲得的期望，因此這一步被稱為E步EM算法(M步)怎樣才能在Θ'的基礎(chǔ)上獲得一個(gè)更好的Θ值呢，一種合理的方法是通過(guò)最大化Q來(lái)實(shí)現(xiàn)，這一步被稱為M步Θ中包含α和μ兩類參數(shù)，以α為例介紹M步的更新算法因?yàn)橛屑s束條件通過(guò)標(biāo)準(zhǔn)的Lagrange優(yōu)化，可得方程組

求解可得文本分類分類是最基本最重要的智能活動(dòng)之一模式識(shí)別系統(tǒng)的主要任務(wù)就是構(gòu)造性能優(yōu)良的分類器分類是靠有監(jiān)督的學(xué)習(xí)實(shí)現(xiàn)的，即通過(guò)有類別標(biāo)注的樣本對(duì)分類器進(jìn)行訓(xùn)練在Web搜索中的應(yīng)用對(duì)網(wǎng)頁(yè)及文檔分類是核心問(wèn)題Spam檢測(cè)情感分類在線廣告

k-NN分類器利用k個(gè)與未知樣本最接近的已知樣本的類別來(lái)投票決定未知樣本的類別兩個(gè)步驟:尋找未知樣本的k個(gè)最近鄰(測(cè)度問(wèn)題)利用k近鄰的類別對(duì)未知樣本的類別進(jìn)行投票預(yù)測(cè)只需對(duì)訓(xùn)練樣本進(jìn)行標(biāo)注，不需要進(jìn)行別的訓(xùn)練k參數(shù)選擇是最大問(wèn)題計(jì)算和存儲(chǔ)開(kāi)銷通常很大Bayes分類器基于Bayes規(guī)則的分類器，理論與應(yīng)用均非常重要假設(shè)每個(gè)文檔只屬于一個(gè)類別，并按如下條件建模每個(gè)類c都有一個(gè)先驗(yàn)概率P(c)對(duì)于每個(gè)類c，存在條件文檔分布P(d|c)則，生成類c中的文檔d的概率等于P(d|c)P(c)，而給定文檔d,d來(lái)自類c的(后驗(yàn))概率后驗(yàn)概率的估計(jì)類條件詞分布P(d|c)通過(guò)對(duì)模型參數(shù)Θ的估計(jì)來(lái)獲得通過(guò)觀察訓(xùn)練樣本集D，可以獲得Θ的后驗(yàn)分布P(Θ|D)從而后驗(yàn)概率P(c|d)可表示為通行的方法是用Θ的最大似然值來(lái)近似上述在P(Θ|D)分布上的求和計(jì)算樸素Bayes模型假設(shè)樣本的各維特征之間是相互獨(dú)立的應(yīng)用在文本分類中，假設(shè)詞匯之間相互獨(dú)立以二值文檔概率模型為例為簡(jiǎn)化計(jì)算，將上式改寫(xiě)為上式的第二個(gè)乘積與d無(wú)關(guān)可以預(yù)先計(jì)算利用樸素Bayes模型需進(jìn)行參數(shù)平滑，以防零概率事件最大熵原理最大熵原理：當(dāng)需要對(duì)事物進(jìn)行預(yù)測(cè)時(shí)，所做的預(yù)測(cè)應(yīng)當(dāng)滿足全部已知的條件，而對(duì)未知的情況不要做任何主觀假設(shè)(以保證概率分布的信息熵最大)假設(shè)有訓(xùn)練數(shù)據(jù){(di,ci),i=1,…,n}P(c|d)的最大熵模型可通過(guò)一些反映已知條件的特征函數(shù)來(lái)建立，每個(gè)特征fj的期望為通過(guò)訓(xùn)練數(shù)據(jù)可獲得如下約束：最大熵分類器在滿足已知約束條件下利用最大熵原理求解P(c|d)利用Lagrange乘子法，為對(duì)應(yīng)每個(gè)特征的約束設(shè)一個(gè)Lagrange乘子λi，所有乘子構(gòu)成集合Λ，構(gòu)造函數(shù)通過(guò)最大化G，可獲得：在文本分類應(yīng)用中，通常為每個(gè)組合(c,t)選擇一個(gè)特征區(qū)分式分類器區(qū)分式分類器不去探究概率分布P(c|d)，而是直接將文檔特征向量映射為類別標(biāo)簽例如，一種構(gòu)造區(qū)分式二元分類器的方法是：在特征空間中找到一個(gè)向量α，使得文檔d的類別標(biāo)簽等于線性最小二乘回歸是獲得上述分類器參數(shù)α和b的有效方法它利用訓(xùn)練數(shù)據(jù){(di,ci),i=1,…,n}，通過(guò)最小化類標(biāo)簽預(yù)測(cè)的均方誤差求解參數(shù)，即最小化誤差SVM基本思想是最大化分類面兩側(cè)的樣本距超平面的最小距離建立在統(tǒng)計(jì)學(xué)習(xí)的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則基礎(chǔ)上文檔向量空間中線性判別函數(shù)的一般形式為g(d)=α·d+b分類面方程為α·d+b=0SVM的優(yōu)化目標(biāo)將判別函數(shù)歸一化，即使離分類面最近的樣本的|g(d)|=1，則分類間隔等于2/‖α‖使間隔最大等價(jià)于使‖α‖最小而要求H對(duì)所有樣本正確分類，應(yīng)使引入正的松弛因子ξi允許錯(cuò)分樣本的存在，則從而，尋找最優(yōu)分類面問(wèn)題可表示為如下二次優(yōu)化問(wèn)題SVM的求解利用Lagrange優(yōu)化方法，可將式SVM的優(yōu)化問(wèn)題轉(zhuǎn)化為如下對(duì)偶問(wèn)題上式的解中，只有少數(shù)λi不為零，它們所對(duì)應(yīng)的樣本就是支持向量，分類閾值b*可利用最優(yōu)分類面方程通過(guò)兩類中任意一對(duì)支持向量求得最終，文檔d的最優(yōu)分類函數(shù)為非線性SVM對(duì)于非線性可分的情況，可以用一個(gè)非線性映射Φ將樣本映射到高維特征空間中，使之在高維空間中線性可分文本在高維空間的內(nèi)積為Φ(di)·Φ(dj)問(wèn)題是能否找到函數(shù)K，使得K(di·dj)=Φ(di)·Φ(dj)，K被稱為核函數(shù)有了核函數(shù)，非線性SVM的求解就變成最優(yōu)分類函數(shù)變?yōu)槌Ｓ煤撕瘮?shù)多項(xiàng)式核函數(shù)徑向基函數(shù)Sigmoid函數(shù)特征選擇文本聚類和文本分類都以詞作為基本特征來(lái)描述文檔高維文檔特征不僅帶來(lái)高額的運(yùn)算開(kāi)銷，而且會(huì)產(chǎn)生由訓(xùn)練樣本不足所導(dǎo)致的模型不可靠或失效的問(wèn)題特征降維非常重要，特征選擇是方法之一兩類特征選擇算法包含算法:從空集開(kāi)始選擇越來(lái)越多好的特征，直到適當(dāng)為止排除算法:從初始特征集開(kāi)始逐步排除差的特征，直到適當(dāng)為止包含算法算法1)對(duì)每個(gè)詞，計(jì)算其類區(qū)分性測(cè)度2)按區(qū)分性測(cè)度對(duì)詞進(jìn)行降序排序3)保留最好的n個(gè)詞作為特征用于表達(dá)文檔各個(gè)詞的類區(qū)分性一般是獨(dú)立計(jì)算的，因此這類算法具有貪心(greedy)的特點(diǎn)區(qū)分性測(cè)度是關(guān)鍵常用測(cè)度包括χ2、互信息、Fisher鑒別指數(shù)等χ2測(cè)度以二類問(wèn)題為例，設(shè)k00,k01分別為類0中不包含/包含詞t的文檔數(shù)k10

,k11分別為類1中不包含/包含詞t的文檔數(shù)n=k00+k01+k10+k11P(C=0)=(k00+k01)/n…定義χ2越大，類與詞之間的相關(guān)性也越大互信息通過(guò)互信息計(jì)算文檔類與詞之間的相關(guān)性互信息通過(guò)P(x,y)對(duì)P(x)P(y)的偏離程度對(duì)隨機(jī)變量之間的依賴程度進(jìn)行測(cè)量如果隨機(jī)變量X和Y相互獨(dú)立，則對(duì)于所有的取值x和yP(x,y)/P(x)P(y)=1因此，定義互信息為Fisher鑒別以二類學(xué)習(xí)問(wèn)題為例，令X和Y分別表示一類向量的集合。向量的元素可以是令向量長(zhǎng)度歸一的實(shí)數(shù)Fisher鑒別在尋找一種映射α*，它使得X和Y兩個(gè)數(shù)據(jù)集被映射到二者質(zhì)心間的距離相對(duì)集合內(nèi)數(shù)據(jù)的展開(kāi)幅度達(dá)到最大的方向上，即Fisher鑒別指數(shù)Fisher鑒別是一種變換，具有破壞特征稀疏性的特點(diǎn)將每個(gè)詞t都看作為一個(gè)候選的方向，即令

αt=(0,…,1,…,0)T，即1只在詞t的位置出現(xiàn)，定義t的Fisher鑒別指數(shù)為由于αt的特殊形式，上式可簡(jiǎn)化為

對(duì)于多類問(wèn)題

排除算法排除算法從全部詞特征集T開(kāi)始逐步對(duì)“無(wú)用”特征進(jìn)行排除，直至獲得一個(gè)滿意的特征子集F排除算法的核心思想是盡量保持P(C

|T)與P(C|F)的相似性，因?yàn)榉诸惻c聚類可以基于類(C)的特征條件概率分布來(lái)設(shè)計(jì)算法P(C

|T)與P(C|F)的相似性可用KL距離來(lái)度量如果P(P=p|Q=q，R=r)=P(P=p|R=r)，則稱P在R條件下獨(dú)立于Q排除算法的核心是尋找類與特征之間的條件獨(dú)立關(guān)系排除算法復(fù)雜度高，優(yōu)點(diǎn)是考慮了特征之間的相關(guān)性特征維數(shù)確認(rèn)Validation:取多少維特征最佳普通確認(rèn)訓(xùn)練數(shù)據(jù)被分為兩部分，分別用于特征排序和測(cè)試交叉確認(rèn):留一法(Leave-One-Out)訓(xùn)練數(shù)據(jù)較少時(shí)使用每次留出一個(gè)樣本用于測(cè)試特征變換通過(guò)數(shù)學(xué)變換對(duì)原始特征進(jìn)行不同的線性或非線性組合，從新產(chǎn)生的組合中挑選好特征本質(zhì)是不同域或空間之間的映射目的是找到能夠用更低維度“緊湊”地表達(dá)文檔數(shù)據(jù)的空間，同時(shí)，在新空間中，文檔之間仍然保持在原空間的親疏關(guān)系只要能起到特征降維和保持文檔之間原有距離的效果的各種數(shù)學(xué)變換都可應(yīng)用于文檔特征變換Fourier、Wavelet、PCA、LDA、流形分析SOM和LSI具有典型意義SOM(Self-OrganizingMap)輸入數(shù)據(jù)并聯(lián)地饋入到一維或二維排列的神經(jīng)元陣列，將多維連續(xù)數(shù)據(jù)空間映射到一維或二維離散數(shù)據(jù)空間神經(jīng)元間的拓?fù)渚嚯x代表使其興奮的數(shù)據(jù)在原空間中的親疏關(guān)系，使同一神經(jīng)元興奮的數(shù)據(jù)被認(rèn)為是一類工作過(guò)程分為競(jìng)爭(zhēng)、協(xié)作和權(quán)值調(diào)整三個(gè)階段一個(gè)作用是將檢索回來(lái)的文檔的相似性在二維平面上進(jìn)行可視化LSI(LatentSemanticIndex)是奇異值分解SVD在文本特征矩陣中應(yīng)用的產(chǎn)物每個(gè)LSI都是所有原始特征(詞)的線性組合，因而具有潛在的語(yǔ)義對(duì)于由特征詞集合T所描述的文檔集合D，令A(yù)={aij}為詞-文檔矩陣，i=1,…,|T|,j=1,…|D|A中的每一列對(duì)應(yīng)一個(gè)文檔的VSM矩陣A的秩遠(yuǎn)小于min{|T|,|D|}，可用SVD進(jìn)行緊致表達(dá)LSI的意義(ATA)|D|×|D|的元素可被解釋為兩個(gè)文檔之間的相似性(AAT)|T|×|T|的元素可被解釋為兩個(gè)詞之間的相似性A的SVD使上述兩個(gè)矩陣變?yōu)?VΣ2VT)|D|×|D|和(UΣ2UT)|T|×|T|V的第d行是文檔d的精煉表示,U的第t行是詞t的精煉表示兩種精煉表示都是r維空間中的向量這意味著，可以只用r個(gè)LSI(而不是|T|個(gè)詞)就能表示一個(gè)文檔，還可以只用r個(gè)LSI(而不是|D|個(gè)文檔)來(lái)表示一個(gè)詞LSI的本質(zhì)是計(jì)算矩陣U、V和ΣU和V分別是(AAT)|T|×|T|和(ATA)|D|×|D|的特征向量矩陣Σ是(AAT)|T|×|T|和(ATA)|D|×|D|的公共特征值矩陣LSI的應(yīng)用在應(yīng)用LSI進(jìn)行特征變換的系統(tǒng)中，將一個(gè)查詢q按下式投射到LSI空間，與r維文檔進(jìn)行相似度計(jì)算具體實(shí)現(xiàn)一個(gè)LSI文檔檢索系統(tǒng)時(shí)，并不需要保留所有r個(gè)特征值。而一般只取最大的200到300個(gè)特征值LSI通常會(huì)在precision和recall兩個(gè)指標(biāo)上同時(shí)改善系統(tǒng)但計(jì)算復(fù)雜度比較高，對(duì)一個(gè)104規(guī)模的文檔集計(jì)算LSI的耗時(shí)大約在小時(shí)量級(jí)Web搜索

第3章圖像檢索文本自動(dòng)標(biāo)注物體識(shí)別文字識(shí)別人臉檢測(cè)與識(shí)別視頻檢索引言Web圖像搜索近年來(lái)已經(jīng)成為研究開(kāi)發(fā)的熱點(diǎn)圖像文檔分圖片和視頻兩種，格式多樣，常包含文本和語(yǔ)音信息查詢的兩種方法:關(guān)鍵詞查詢和示例查詢關(guān)鍵詞查詢可以采用現(xiàn)有的文本檢索的技術(shù)架構(gòu)，但先要對(duì)圖像進(jìn)行文本標(biāo)注示例查詢可以提交基于視覺(jué)特征的準(zhǔn)確的查詢請(qǐng)求，但提交查詢不夠方便，匹配算法的計(jì)算量大圖像檢索系統(tǒng)中的關(guān)鍵技術(shù)都是圖像的分類物體識(shí)別、文字識(shí)別、人臉檢測(cè)與識(shí)別在圖像檢索中有特別重要的意義圖像檢索的發(fā)展過(guò)程研究始于上世紀(jì)70年代，當(dāng)時(shí)的檢索對(duì)象主要是中小規(guī)模的圖像數(shù)據(jù)庫(kù)人工標(biāo)注索引、關(guān)鍵詞檢索90年代，開(kāi)始研究基于自動(dòng)分析和標(biāo)注的圖像檢索基于低層視覺(jué)特征，即顏色、紋理、形狀等為圖像建立特征向量，三類特征有不同的性質(zhì)使圖像檢索脫離了基于關(guān)鍵詞的檢索框架一個(gè)不太確切的名字:CBIR基于視覺(jué)特征的檢索具有較強(qiáng)的客觀性應(yīng)用效果并不理想，研究熱點(diǎn)轉(zhuǎn)向基于語(yǔ)義的檢索文本自動(dòng)標(biāo)注自動(dòng)地對(duì)圖像中包含的各種物體進(jìn)行標(biāo)注，甚至能夠標(biāo)注其中包含的抽象概念是極富挑戰(zhàn)性的課題從大類標(biāo)注做起圖形類/照片類城市/風(fēng)景室內(nèi)/室外對(duì)檢索有幫助，但信息顆粒太大，信息量太少基于區(qū)域劃分的標(biāo)注基于one-vs-all二值分類器的標(biāo)注有監(jiān)督的多類標(biāo)注基于2DMHMM的二類標(biāo)注通過(guò)有監(jiān)督學(xué)習(xí)建立每類圖像的模型將每類圖像與一個(gè)概念相對(duì)應(yīng)，對(duì)其進(jìn)行包含多詞的人工文本描述，類的特征用2DMHMM描述每幅圖像都由一組按金字塔結(jié)構(gòu)空間排列的不同粒度的特征向量描述在此基礎(chǔ)上獲得每個(gè)圖像類的2DMHMM2DMHMM模型對(duì)兩類信息進(jìn)行抽取不同粒度的特征向量組特征向量組之間的空間關(guān)系特征抽取利用小波變換提取訓(xùn)練圖像的局部特征一幅圖像被劃分為一些4×4像素的塊從圖像塊中抽取6維特征(兩類)塊中像素的3個(gè)平均彩色成分(在LUV亮度/色度空間計(jì)算)小波變換中3個(gè)高頻帶中的紋理特征，每個(gè)特征對(duì)應(yīng)各自頻帶中小波系數(shù)二階矩的平方根以HL頻帶為例，設(shè)其系數(shù)為{ck,l,ck,l+1,ck+1,l,ck+1,l+1}，則其紋理特征為:多粒度統(tǒng)計(jì)建模人工定義概念辭典，對(duì)應(yīng)各概念給出簡(jiǎn)短而重要的描述特征從每幅訓(xùn)練圖像中多粒度抽出，通過(guò)對(duì)本類圖像集內(nèi)多個(gè)特征向量的統(tǒng)計(jì)平均，每個(gè)概念獲得一個(gè)跨粒度的統(tǒng)計(jì)模型基于統(tǒng)計(jì)的文本標(biāo)注用同樣方法抽取待標(biāo)注的圖像的特征向量計(jì)算該特征向量由各個(gè)概念模型產(chǎn)生的可能性根據(jù)可能性最高的若干模型所對(duì)應(yīng)的文本進(jìn)行標(biāo)注圖像建模首先獲得一幅圖像在不同粒度下的多個(gè)副本原始圖像給出最小粒度的副本較大粒度的副本通過(guò)濾掉前一個(gè)副本的高頻信息而依次生成(可利用小波變換的LL頻帶獲得)從一個(gè)特定粒度的塊中計(jì)算出的(子)特征向量被作為2DMHMM的1條多變量數(shù)據(jù)粒度每提高一級(jí)，水平和垂直方向的塊數(shù)減少一半2DHMM—2DMHMM的基礎(chǔ)假設(shè)圖像的特征向量(組)由一個(gè)HMM生成si,j表示塊(i,j)的狀態(tài)，ui,j表示塊(i,j)的特征向量如果i'<i或者i'=i同時(shí)j'<j，稱(i',j')<(i,j)，或者說(shuō)塊(i',j')在塊(i,j)之前2DHMM基于如下兩個(gè)假設(shè)建立1:P(si,j|context)=am,n,l

m=si-1,j,n=si,j-1,l=si,j

context={si’,j’,ui’j’:(i',j')<(i,j)}2:在給定狀態(tài)下特征向量符合Gauss分布，一旦某個(gè)圖像塊的狀態(tài)已知，其特征向量將條件獨(dú)立于其他塊的信息，即每個(gè)狀態(tài)s擁有自己的協(xié)方差矩陣Σs和均值向量μs2DMHMM(1/3)用集合R={1,…,R}表示粒度，R代表最小粒度粒度r的塊標(biāo)號(hào)集合為IN(r)={(i,j):0≤i<w/2R-r,0≤j<z/2R-r}w和z分別是原始圖像的水平和垂直方向的像素?cái)?shù)圖像的特征向量為對(duì)應(yīng)的潛在狀態(tài)為對(duì)應(yīng)的狀態(tài)集合假設(shè)相鄰級(jí)間的統(tǒng)計(jì)依賴關(guān)系符合一階Markov鏈，即給定上一粒度級(jí)的狀態(tài)，則本粒度級(jí)的狀態(tài)條件獨(dú)立于高于上一粒度級(jí)的所有其他粒度級(jí)的狀態(tài)，有2DMHMM(2/3)在給定狀態(tài)下，特征向量條件獨(dú)立于任何其他狀態(tài)及其特征向量，因此一幅圖像所有粒度級(jí)所有圖像塊的狀態(tài)-特征聯(lián)合概率(模型估計(jì)時(shí)要考慮各種狀態(tài)-特征組合)2點(diǎn)假定1:給定r-1粒度級(jí)的狀態(tài)，r粒度級(jí)的圖像塊之間的統(tǒng)計(jì)依賴關(guān)系被限定在具有相同父塊的“兄弟”子塊之間2:給定父塊的狀態(tài)，子塊的狀態(tài)獨(dú)立于與父塊同級(jí)的其他塊的狀態(tài)2DMHMM(3/3)記r-1粒度級(jí)的(k,l)塊在r粒度級(jí)的子塊為根據(jù)以上假設(shè)最終文本標(biāo)注圖像I與一個(gè)圖像類C的相似性通過(guò)由C的2DMHMM模型產(chǎn)生I的對(duì)數(shù)似然度來(lái)估計(jì)獲得圖像I屬于各個(gè)圖像類的似然度后，將其進(jìn)行排序，以找出似然度最高的k個(gè)圖像類，k可以固定，也可以基于似然度閾值選取前k個(gè)類的描述詞是圖像I的候選標(biāo)注詞，如果希望用較少的詞標(biāo)注圖像，則需要一個(gè)篩選機(jī)制假設(shè)標(biāo)注詞T在k個(gè)類中出現(xiàn)j次標(biāo)注詞T在隨機(jī)選取的k個(gè)類中至少出現(xiàn)j次概率近似為p為T(mén)在標(biāo)注中使用的概率，這個(gè)概率越小，T越重要實(shí)驗(yàn)—“男人”概念的訓(xùn)練樣本基于COREL公司6萬(wàn)張照片數(shù)據(jù)庫(kù)實(shí)驗(yàn)—圖像自動(dòng)標(biāo)注實(shí)例有監(jiān)督的多類標(biāo)注SML對(duì)訓(xùn)練圖像逐幅分別標(biāo)注然后聚類的方法曾是流行的多類標(biāo)注策略基于標(biāo)注詞和視覺(jué)特征聚類以獲得每個(gè)潛在類別的標(biāo)注詞-視覺(jué)特征的聯(lián)合分布伸縮性好，但聯(lián)合分布估計(jì)較困難SML結(jié)合有監(jiān)督二類標(biāo)注和無(wú)監(jiān)督多類標(biāo)注的優(yōu)點(diǎn)，將圖像文本標(biāo)注定義為多個(gè)圖像類的分類問(wèn)題避免了串行獨(dú)立地進(jìn)行多個(gè)二值分類保留了有監(jiān)督標(biāo)注在分類和檢索意義上的優(yōu)化特性SML的基本過(guò)程a)圖像特征抽取b)圖像語(yǔ)義類建模c)圖像標(biāo)注或檢索SML的訓(xùn)練及標(biāo)注第i(i=1,…,T)個(gè)標(biāo)注詞對(duì)應(yīng)第i個(gè)圖像語(yǔ)義類第i類訓(xùn)練圖像集合由包含第i個(gè)圖像語(yǔ)義的所有圖像構(gòu)成一幅圖像可能作為多個(gè)類的訓(xùn)練樣本設(shè)從測(cè)試圖像中抽取的視覺(jué)特征為x，則標(biāo)注方法為將圖像文本標(biāo)注變成了一個(gè)多分類問(wèn)題降低了模型估計(jì)的計(jì)算量回避了二分類模型需估計(jì)非類(nonclass)分布的計(jì)算瓶頸后驗(yàn)概率自然成為選擇標(biāo)注詞的順序無(wú)圖像分割的類概率分布建模大多數(shù)圖像是由不同的圖像概念共同構(gòu)成的問(wèn)題:不分割圖像，能否估計(jì)圖像概念的視覺(jué)特征分布解決途徑:多實(shí)例學(xué)習(xí)法(multipleinstancelearningperspective)基于正負(fù)樣本口袋(bagsofexamples)進(jìn)行建模每個(gè)口袋是樣本的一個(gè)集合，如果其中至少有一個(gè)正樣本，則被看作是正的，否則被看作是負(fù)的正口袋中的負(fù)樣本趨向于分散在整個(gè)特征空間，而正樣本卻趨向于集中在一個(gè)較小的區(qū)域之中概率密度分布的估計(jì)方法給定包含概念wi的訓(xùn)練圖像數(shù)據(jù)集Di，概念wi的概率密度分布估計(jì)有多種方法直接估計(jì)法:用Di中所有圖像的特征向量構(gòu)成訓(xùn)練集，對(duì)密度函數(shù)進(jìn)行估計(jì)需要較大的存儲(chǔ)開(kāi)銷模型平均法:先對(duì)對(duì)每幅圖像的密度函數(shù)進(jìn)行估計(jì)，然后對(duì)所有密度函數(shù)取平均平均模型的混合分量多，測(cè)試階段耗時(shí)層次結(jié)構(gòu)法:下層子密度函數(shù)是上層父密度函數(shù)的分量組合每幅圖像對(duì)應(yīng)的是子密度函數(shù)語(yǔ)義類對(duì)應(yīng)的是父密度函數(shù)密度函數(shù)參數(shù)的層次推導(dǎo)1:利用|Di|個(gè)樣本獲得|Di|組GMM密度函數(shù)參數(shù)，設(shè)GMM的混合分量為K，則共有K|Di|

組Gauss參數(shù)2:利用擴(kuò)展EM算法將上述K|Di|個(gè)Gauss分量聚類為一個(gè)M分量的混合模型用于GMM分量聚類的擴(kuò)展EM算法M-step:E-step:SML算法(基于GMM-DCT特征)給定圖像-標(biāo)題集合這里，對(duì)每個(gè)語(yǔ)義類w∈L1:建立一個(gè)訓(xùn)練圖像集合TD，TD中所有圖像的標(biāo)題都包含w2:對(duì)于TD中的每幅圖像I將I分解為相互重疊的N個(gè)區(qū)域(大小為8×8，相鄰重疊為2)在YBR空間計(jì)算每個(gè)區(qū)域的DCT，獲得特征x=[xY,xB,xR]通過(guò)EM算法估計(jì)每幅圖像的具有8個(gè)分量的GMM3:通過(guò)擴(kuò)展EM算法獲得64個(gè)GMM分量的語(yǔ)義類w的分布標(biāo)注算法對(duì)于一個(gè)測(cè)試圖像It1:用與訓(xùn)練階段相同的方法抽取It的口袋特征B，

B={x1,…,xN}2:對(duì)于每個(gè)類wi∈L，計(jì)算其中，3:用后驗(yàn)概率logP(wi|B)最大的5個(gè)類wi對(duì)測(cè)試圖像It進(jìn)行標(biāo)注實(shí)驗(yàn)—對(duì)Corel5k/30k的自動(dòng)標(biāo)注物體識(shí)別物體識(shí)別是近十年來(lái)圖像識(shí)別的研究熱點(diǎn)早期，文字、紋理、指紋等識(shí)別通常不考慮光線、色彩、畫(huà)質(zhì)、背景、遮擋、拍攝角度等復(fù)雜問(wèn)題物體識(shí)別的難點(diǎn)集中在類內(nèi)圖像之間存在更大差異研究的主要方面類別建模:核心是物體表達(dá)方法特征抽取:關(guān)鍵域檢測(cè)和特征壓縮模型學(xué)習(xí):計(jì)算復(fù)雜度極高的問(wèn)題星群模型利用概率的方法將物體靈活地表示為一組部件“星群”模型對(duì)遮擋、形變、光照、視角等變化因素有較強(qiáng)的吸收能力假設(shè)一個(gè)物體由若干部件構(gòu)成每個(gè)部件具有特定的外觀，相對(duì)的尺度，和可被遮擋的屬性物體的形狀由各部件的相對(duì)位置描述星群模型是生成概率模型，外觀、尺寸、形狀以及遮擋均由Gauss概率密度函數(shù)建模星群模型的分類策略假設(shè)通過(guò)學(xué)習(xí)已經(jīng)獲得了一個(gè)物體類C的生成模型，部件數(shù)為P、參數(shù)為θ假設(shè)在測(cè)試圖像I中檢測(cè)到了N個(gè)關(guān)鍵域，它們的位置、尺寸和外觀特征向量分別為X、S和A，則Bayes決策參數(shù)通過(guò)包含P個(gè)元素的隨機(jī)向量h，似然函數(shù)可分解為h指示部件與關(guān)鍵域的對(duì)應(yīng)關(guān)系，元素的取值為0,1,…N集合H為全部有效的對(duì)應(yīng)方案，|H|的數(shù)量級(jí)為O(NP)討論似然比因子中的符號(hào)d=sign(h)，表示各個(gè)部件遮擋狀態(tài)的二值向量f=sum(d)，被分配到前景(物體)上關(guān)鍵域數(shù)n=N–f，被分配到背景上的關(guān)鍵域數(shù)h0:表示h中的所有元素都為0，即假設(shè)無(wú)前景部件，所有關(guān)鍵域都來(lái)自背景外觀似然比每個(gè)關(guān)鍵域的外觀被表示為特征空間中的一點(diǎn)每個(gè)部件p在特征空間中有一個(gè)與其他部件相互獨(dú)立的Gauss概率密度函數(shù)，參數(shù)為背景的Gauss密度函數(shù)參數(shù)為假設(shè)Vp和Vbg斜方差矩陣均為對(duì)角陣被選為部件的關(guān)鍵域由對(duì)應(yīng)的部件密度函數(shù)來(lái)估計(jì)，未被選為部件的關(guān)鍵域由背景密度函數(shù)來(lái)估計(jì)，則形狀似然比在給出假設(shè)的條件下，物體的形狀可由對(duì)應(yīng)各部件的關(guān)鍵域的位置來(lái)確定引入一個(gè)聯(lián)合Gauss密度函數(shù)來(lái)描述關(guān)鍵域的相對(duì)位置，即物體的形狀，參數(shù)為所有未被分配到部件上的關(guān)鍵域被視為于背景背景模型假設(shè)關(guān)鍵域在整個(gè)圖像面積α上均勻分布如果某個(gè)部件被遮擋，將不被考慮在密度函數(shù)之內(nèi)根據(jù)以上假設(shè)相對(duì)尺度似然比每個(gè)部件p相對(duì)于參考幀的尺度由一個(gè)的Gauss密度函數(shù)建模，參數(shù)為假設(shè)各部件的尺度之間相互獨(dú)立，背景中關(guān)鍵域的尺度在r區(qū)間內(nèi)均勻分布，則假設(shè)似然比與關(guān)鍵域檢測(cè)器的統(tǒng)計(jì)特性和遮擋模式有關(guān)等式右邊的第一項(xiàng)是利用均值為M的Poisson分布對(duì)背景的關(guān)鍵域數(shù)量進(jìn)行建模nCr(N,f)表示從N中取f的組合數(shù)最后一項(xiàng)是模型的一個(gè)參數(shù)，為描述所有遮擋模式的尺寸為2P的一個(gè)概率表關(guān)鍵域檢測(cè)Kadir檢測(cè)器基本思想:在各種不同的位置和尺度上尋找特點(diǎn)突出的區(qū)域?qū)D像中的每個(gè)點(diǎn)，計(jì)算半徑為s的區(qū)域中亮度的分布P(I)計(jì)算對(duì)應(yīng)各個(gè)尺度s的熵H(s)根據(jù)H(s)的局部極大值獲得候選區(qū)域每個(gè)候選區(qū)域的“突出性”測(cè)度:每個(gè)關(guān)鍵域由其中心和半徑所定義例子:查找黑暗背景中的一個(gè)亮點(diǎn)關(guān)鍵域的特征描述關(guān)鍵域的特征從位置、尺寸和外觀等方面描述中心坐標(biāo)用X描述半徑尺寸用S描述外觀特征A的提取將關(guān)鍵域縮放成11×11的區(qū)域，形成121維特征意味著要估計(jì)121組Gauss的均值和方差采用PCA提取10至15個(gè)主成分作為其外觀特征A從一幅圖像中通?？蓹z測(cè)出幾十個(gè)關(guān)鍵域模型學(xué)習(xí)(參數(shù)估計(jì))物體類模型由參數(shù)θ={μ,Σ,c,V,t,U,M,p(d|

θ)}描述μ,Σ分別為形狀密度函數(shù)的均值向量和協(xié)方差矩陣c,V分別為各部件外觀的均值向量和方差向量t,U分別為各部件的相對(duì)尺度的均值和方差M為背景中關(guān)鍵域數(shù)量的Poisson分布參數(shù)p(d|

θ)為各種遮擋模式的概率通過(guò)所有訓(xùn)練圖像的特征X，S和A進(jìn)行參數(shù)估計(jì)可采用EM算法完成，需要計(jì)算每個(gè)假設(shè)h(共O(NP)個(gè))的似然度，學(xué)習(xí)效率是突出問(wèn)題實(shí)驗(yàn)設(shè)計(jì)摩托車、飛機(jī)、人臉、轎車(側(cè)面)、轎車(后面)、花豹、背景共7個(gè)數(shù)據(jù)集，分成相等的兩部分，分別用于訓(xùn)練和測(cè)試測(cè)試的任務(wù)是判斷圖像中是否包含指定的物體性能指標(biāo)為ROC等錯(cuò)誤率“誤陽(yáng)率”與“誤陰率”相等時(shí)的性能指標(biāo)參數(shù):PCA外觀特征數(shù)k=15，部件數(shù)P=6，每幅圖像平均關(guān)鍵域數(shù)N=20人臉模型人臉測(cè)試實(shí)驗(yàn)?zāi)Ｐ偷膮^(qū)分性和尺度不變性異構(gòu)星狀模型HSM星群模型的問(wèn)題形狀模型中的聯(lián)合概率導(dǎo)致計(jì)算量呈指數(shù)膨脹，學(xué)習(xí)和識(shí)別的計(jì)算復(fù)雜度均為O(NP)由于N和P的數(shù)量受限(上面的實(shí)驗(yàn)中N=20,P=6)，模型只能通過(guò)圖像的少數(shù)代表區(qū)域進(jìn)行學(xué)習(xí)只采用了一種基于區(qū)域的檢測(cè)器模型中的參數(shù)較多HSM的提出顯著緩解了上述問(wèn)題可采用的部件數(shù)和關(guān)鍵域數(shù)都有了實(shí)質(zhì)性的提高采用多種不同類型的關(guān)鍵域檢測(cè)器識(shí)別階段可采用全面搜索的方式HSM的核心改進(jìn)不再用聯(lián)合概率描述物體的各個(gè)部件的位置關(guān)系，即形狀(這是導(dǎo)致模型復(fù)雜的決定因素)HSM提出了一個(gè)簡(jiǎn)化的配置模型設(shè)置一個(gè)基準(zhǔn)部件，為非基準(zhǔn)部件的位置提供約束條件設(shè)定基準(zhǔn)部件后，非基準(zhǔn)部件之間相互獨(dú)立，使計(jì)算復(fù)雜度從O(NP)降至O(N2P)全連接模型與星狀模型之間的區(qū)別HSM的檢測(cè)器(a)Curve(b)Kadir(c)多尺度Harris基于梯度的PCA特征關(guān)鍵域的提取Kadir和多尺度Harris本身就是區(qū)域檢測(cè)器Curve檢測(cè)器采用Canny算子提取邊緣，丟棄直線條，將曲線條的中心點(diǎn)設(shè)為關(guān)鍵域的中心，長(zhǎng)度設(shè)為關(guān)鍵域的長(zhǎng)和寬將關(guān)鍵域縮放為k×k圖像塊后，提取2k2維的歸一化梯度向量，前k2維是x方向的導(dǎo)數(shù)，后k2維是y方向的導(dǎo)數(shù)通過(guò)固定基函數(shù)的PCA將梯度向量變換為一個(gè)d維向量加上圖像塊原有的能量和PCA重建誤差2個(gè)參數(shù)，構(gòu)成d+2維的向量HSM的學(xué)習(xí)采用EM算法為了能夠用更多的檢測(cè)區(qū)域?qū)W習(xí)更多的部件，要對(duì)HSM的學(xué)習(xí)進(jìn)行一些約束，以避免組合爆炸除了基準(zhǔn)部件外，部件要按坐標(biāo)(如x方向)順序編號(hào)每個(gè)部件只允許選擇指定類型的特征各部件的特征類型通過(guò)確認(rèn)樣本選擇HSM模型的學(xué)習(xí)效率提高了約144倍訓(xùn)練一個(gè)模型的時(shí)間:原來(lái)24小時(shí)

現(xiàn)在10分鐘HSM的窮舉識(shí)別HSM還可以采用窮舉識(shí)別(exhaustiverecognition)HSM的外觀密度函數(shù)給出了系統(tǒng)要尋找的圖像區(qū)域的模型將外觀密度函數(shù)在圖像上窮舉式地進(jìn)行匹配，即在每個(gè)位置和尺寸上，計(jì)算各部件的似然比利用星狀模型的在位置制約上的優(yōu)勢(shì)并采用有效的匹配方法找出在外觀和位置上全局最優(yōu)的區(qū)域文字識(shí)別文字識(shí)別對(duì)實(shí)現(xiàn)基于語(yǔ)義的圖像檢索有很大幫助文字識(shí)別是模式識(shí)別最早的研究領(lǐng)域目前，文字識(shí)別的研究重點(diǎn)已轉(zhuǎn)向?qū)Ｓ妙I(lǐng)域圖像中的文字識(shí)別引起了廣泛關(guān)注不但可以幫助圖像檢索，而且需要克服許多新的問(wèn)題，如文字的檢測(cè)、切分、傾斜校正、以及處理效率等文字識(shí)別的技術(shù)種類在線/離線手寫(xiě)/印刷漢字/外文……離線文字識(shí)別系統(tǒng)典型的離線文字識(shí)別系統(tǒng)由文字圖像獲取、預(yù)處理、特征抽取、分類識(shí)別和后處理等模塊組成文字圖像獲取:采用光學(xué)設(shè)備獲得文字的像素描述預(yù)處理:包括二值化、去噪聲、傾斜校正、文字切分和尺寸歸一化等特征抽取:方向線素特征分類識(shí)別:可采用模板匹配、Bayes、kNN、SVM、BP神經(jīng)網(wǎng)絡(luò)等多種分類器后處理:基于統(tǒng)計(jì)語(yǔ)言模型的后處理最常見(jiàn)樣本庫(kù)—HCL2000面向國(guó)標(biāo)一級(jí)3755個(gè)漢字每個(gè)漢字有來(lái)自不同書(shū)寫(xiě)者的1600多個(gè)樣本樣本庫(kù)與書(shū)寫(xiě)者信息庫(kù)相互溝通非線性歸一化非線性歸一化的基本思想是通過(guò)某種非線性變換，使文字筆劃的空間布局趨于均衡方法:基于點(diǎn)密度均衡、基于筆劃穿越數(shù)均衡和基于筆劃間隔均衡等多種例:基于筆劃間隔均衡令FH(i,j)、FV(i,j)為(i,j)點(diǎn)處水平和垂直方向相鄰筆劃距離的倒數(shù)，即余弦整形變換采用不同的余弦函數(shù)，實(shí)現(xiàn)對(duì)漢字在水平和垂直兩個(gè)方向上，左推、右推以及中心擴(kuò)展的變換，以產(chǎn)生所需要的字形方向線素特征抽取方向線素由水平、垂直、＋45°或－45°方向上的相鄰兩個(gè)黑像素構(gòu)成粗分類特征用5×5、細(xì)分類特征的8×8+7×7二重劃分將文字圖像分別分割為25和113個(gè)小區(qū)域提取方向線素特征的掩模漸進(jìn)計(jì)算的馬氏距離分類器馬氏距離（Mahalanobisdistance）分類器得到了越來(lái)越廣泛的應(yīng)用，精度高，但運(yùn)算量大是特征為Gauss分布，各類別的先驗(yàn)概率相等條件下的Bayes分類器，一般形式如下

d(x,μ)=(x-μ)TΣ-1(x-μ)馬氏距離計(jì)算方法將正定的Σ分解為L(zhǎng)DLT

形式，L:對(duì)角線元素為1的下三角陣，D:對(duì)角線元素為正的對(duì)角陣定義一維列向量w=L-1(x-μ)單調(diào)遞增的漸進(jìn)計(jì)算:文字切分算法圖像中的文字切分是文字識(shí)別的基礎(chǔ)，很有難度常見(jiàn)的算法滴水(Drop-Falling)算法Max-min算法動(dòng)態(tài)規(guī)劃(DynamicProgramming)算法問(wèn)題:缺乏針對(duì)性、盲目搜索、局部最優(yōu)基于模具的手寫(xiě)字符串切分算法將字符的切分過(guò)程變?yōu)楦鞣N模具的試用和優(yōu)選過(guò)程

Adaboost人臉檢測(cè)算法采用Boosting算法進(jìn)行人臉檢測(cè)是近年來(lái)最流行方法Boosting在學(xué)習(xí)中，對(duì)誤判的訓(xùn)練樣本賦予較大的權(quán)值，讓算法在后續(xù)的過(guò)程中重點(diǎn)對(duì)這些樣本進(jìn)行學(xué)習(xí)[Viola01]將Boosting、Haar-like特征、積分圖像和級(jí)聯(lián)結(jié)構(gòu)相結(jié)合，在精度和速度兩方面同時(shí)獲得了突破Haar-like特征通過(guò)計(jì)算相鄰矩形中像素累積值的差獲得相鄰矩形可以為兩個(gè)、三個(gè)或四個(gè)，相鄰的方向可以是水平的，也可以是垂直的

積分圖像ii(x,y)坐標(biāo)點(diǎn)(x,y)的積分圖像被定義為從圖像坐標(biāo)原點(diǎn)(左上角點(diǎn))到(x,y)點(diǎn)所形成的圖像區(qū)域中所有像素的累積值根據(jù)這個(gè)定義，可以只遍歷圖像一次就能獲得所有點(diǎn)的積分圖像，算法采用如下迭代公式

s(x,y)=s(x,y-1)+i(x,y)

ii(x,y)=ii(x-1,y)+s(x,y)

其中，s(x,y)為行積分，并且s(x,-1)=0,ii(-1,y)=0例:A區(qū)域的像素累積值等于1點(diǎn)的積分圖像，B區(qū)域的等于2點(diǎn)的積分圖像減去1點(diǎn)的積分圖像，等等

檢測(cè)器的學(xué)習(xí)算法

給定訓(xùn)練樣本集{(xi,yi):i=1,…,n}初始化各樣本的分布權(quán)重對(duì)t=1,…,T權(quán)重歸一化用每個(gè)特征j,構(gòu)造分類器hj，誤識(shí)率選擇誤識(shí)率最小的分類器ht更新權(quán)重如果xi被正確分類ei=0，否則為1，最終的強(qiáng)分類器為這里常見(jiàn)的人臉識(shí)別算法基于觀測(cè)特征的算法早期的人臉識(shí)別主要采用觀測(cè)空間中的直觀特征研究眼、鼻、口、耳、額、頰等器官的幾何描述及匹配EGM(ElasticGraphMatching)在上世紀(jì)90年代后期被引入人臉識(shí)別特征的描述方法:Gabor小波、HMM、神經(jīng)網(wǎng)絡(luò)基于變換特征的算法將觀測(cè)空間中的圖像進(jìn)行代數(shù)變換，在變換空間進(jìn)行特征抽取和匹配變換方法:PCA、SVD、LDA、ICA、基于核的變換對(duì)于一些限定變化因素的數(shù)據(jù)庫(kù)，許多算法得出了超過(guò)99%的識(shí)別率

非限定性人臉識(shí)別算法—視覺(jué)機(jī)制生物視覺(jué)中的兩個(gè)重要機(jī)制視覺(jué)皮層中的結(jié)構(gòu)特征(texturefeature)選擇捕捉圖像中特征的位置、朝向、空間頻率等特性視網(wǎng)模中的中心環(huán)繞(center-surround)過(guò)濾由于光線變化所引起的圖像之間的亮度差結(jié)構(gòu)特征選擇的模型是用一族二維Gabor小波函數(shù)對(duì)圖像進(jìn)行卷積

中心環(huán)繞機(jī)制可以用自商操作(self-quotientoperator)來(lái)建模可以模擬上述機(jī)制抽取人臉圖像的RTF和RCFR:Retinal，T:Texture，C:Color，F(xiàn):FeatureRTF特征提取

a.外觀圖像I(z)(1282)b.Gauss核F(z)c.低通圖像F(z)*I(z)d.初級(jí)視覺(jué)圖像RI(z)e.16×16采樣網(wǎng)格f.格中的權(quán)重wv(z,zi)g.純臉圖像RTFh.全臉圖像RTFRTF={

}RCF特征提取

令I(lǐng)R(z)、IG(z)、IB(z)分別表示圖像的R、G、B成分，定義IQ(z)=2.11IR(z)–5.22IG(z)+3.11IB(z)ICr(z)=11.1IR(z)–9.37IG(z)–1.82IB(z)對(duì)R成分進(jìn)行中心環(huán)繞處理以獲得更好的光照不變性對(duì)上述三個(gè)圖像成分進(jìn)行低通濾波，最終將純臉和

全臉的空間分辯率分別降至

42×42和36×30增量式魯棒性鑒別降維(1/2)當(dāng)前最流行的降維方法是“PCA+LDA”魯棒性線性鑒別分析模型RDM首先計(jì)算Sw的特征向量矩陣Φ和特征值對(duì)角矩陣Θ試圖利用ΦΘ-1/2構(gòu)成類內(nèi)白化空間各個(gè)方向上的坐標(biāo)都被本方向的分散度所伸縮有將分散過(guò)小的方向的數(shù)據(jù)差異性極度放大的問(wèn)題RDM對(duì)特征值對(duì)角矩陣進(jìn)行正則化來(lái)解決這個(gè)問(wèn)題

增量式魯棒性鑒別降維(2/2)在由定義的正則化白化空間中類間分散矩陣被變換為設(shè)Vb的特征向量矩陣為，則

為解決大數(shù)據(jù)量訓(xùn)練問(wèn)題，引入RDM的可伸縮版本IRDM應(yīng)用SKL(SequentialKarhunen-Loeve)變換進(jìn)行數(shù)據(jù)降維多線索融合的識(shí)別系統(tǒng)

NC—NormalizedCosinesimilarityS—SimilarityPFS—PureFaceSub-systemFFS—FullFaceSub-system視頻檢索視頻檢索已成為一個(gè)與圖像檢索相對(duì)獨(dú)立的技術(shù)領(lǐng)域2001年TREC會(huì)議啟動(dòng)了視頻檢索任務(wù)TRECVID鏡頭切分、高層特征抽取、檢索系統(tǒng)、視頻摘要等鏡頭切分:物理層上的視頻切分和組織切分輔助信息:主持人鏡頭、字幕、受訪人鏡頭、說(shuō)話人的聲音、語(yǔ)音內(nèi)容、背景音樂(lè)等高層特征

高層特征音頻特征視覺(jué)特征靜態(tài)特征運(yùn)動(dòng)特征場(chǎng)景特征物體特征鏡頭切分對(duì)突變(Cut)式鏡頭切換，簡(jiǎn)單的基于幀間差的算法就可以獲得較高的精度但漸變式鏡頭切換，簡(jiǎn)單的幀間差算法難以應(yīng)對(duì)AT&T提出了分別針對(duì)不同切換方式的多種檢測(cè)算法

特征抽取

幀內(nèi)特征:ROI中紅、綠、藍(lán)及亮度通道的直方圖統(tǒng)計(jì)量直方圖的均值、方差、陡峭度、平坦度、動(dòng)態(tài)區(qū)域等兩組幀間特征:分別反映當(dāng)前幀與前1和前6幀之間的變化導(dǎo)數(shù)特征:直方圖均值的差值、直方圖方差的差值、直方圖動(dòng)態(tài)區(qū)域的差值等運(yùn)動(dòng)特征:對(duì)于前幀的中心子塊(32*32)，查找在當(dāng)前幀中的最佳匹配位置，抽取運(yùn)動(dòng)向量MVk、最小匹配誤差MEk和匹配率MRk等?；谒?4個(gè)塊的運(yùn)動(dòng)特征，選擇支配性的運(yùn)動(dòng)向量及其所占的比例作為幀一級(jí)的運(yùn)動(dòng)特征基于FSM的鏡頭切換檢測(cè)器3個(gè)狀態(tài)變量取值為0～N的當(dāng)前狀態(tài)變量state-id，state-id=0表示初始狀態(tài)，state-id=1用于指示檢測(cè)到鏡頭切換，其他值用于表示各個(gè)FSM的內(nèi)部狀態(tài)前一鏡頭的最后一幀start-frame新鏡頭的第一幀end-frame例:Cut檢測(cè)器關(guān)鍵變量:AverageMEAverageME=0.85AverageME+0.15AverageMEA

一種以人物為中心的視頻摘要系統(tǒng)系統(tǒng)在鏡頭切分、人臉檢測(cè)、語(yǔ)音/非語(yǔ)音鑒別、鏡頭聚類等多種技術(shù)支撐下進(jìn)行視頻摘要

基本流程視頻被切分為若干鏡頭從每個(gè)鏡頭中選取3個(gè)關(guān)鍵幀基于關(guān)鍵幀之間的差異性計(jì)算鏡頭之間的距離矩陣，基于距離矩陣對(duì)鏡頭進(jìn)行聚類從每個(gè)聚合類中選出時(shí)間最長(zhǎng)的鏡頭，將摘要的總時(shí)間長(zhǎng)度按比例分配給每個(gè)選出的鏡頭根據(jù)分配的時(shí)間長(zhǎng)度從每個(gè)選出的鏡頭中找出一個(gè)重要連續(xù)片段將這些片段按時(shí)間順序進(jìn)行串接形成最終的摘要

鏡頭聚類及摘要生成鏡頭聚類的核心問(wèn)題是計(jì)算兩個(gè)鏡頭之間的距離設(shè)鏡頭X和Y的3個(gè)代表幀分別為{x1,x2,x3}和{y1,y2,y3}xi和yj的距離dij用它們之間的匹配誤差來(lái)表示則鏡頭之間的距離D(X,Y)

摘要生成時(shí)，要根據(jù)所限定的摘要最大長(zhǎng)度分配各個(gè)代表鏡頭的摘要長(zhǎng)度各鏡頭的重要度根據(jù)其是否包含人臉及語(yǔ)音來(lái)打分從每個(gè)代表鏡頭中摘取限定長(zhǎng)度的片段，最簡(jiǎn)單直接的方法是選取累積重要度最高的一個(gè)連續(xù)片段Web搜索

第4章音頻檢索聲學(xué)特征提取

HMM模型連續(xù)語(yǔ)音識(shí)別系統(tǒng)語(yǔ)音關(guān)鍵詞發(fā)現(xiàn)技術(shù)語(yǔ)音詞匯檢測(cè)技術(shù)非語(yǔ)音音頻檢索音樂(lè)檢索音頻檢索的策略音頻檢索起步較晚，但目前已經(jīng)成為一個(gè)新熱點(diǎn)語(yǔ)音類音頻檢索的一個(gè)自然策略是語(yǔ)音識(shí)別

文本檢索全文的轉(zhuǎn)換或關(guān)鍵詞的轉(zhuǎn)換直接基于聲學(xué)特征進(jìn)行檢索的策略越來(lái)越受到重視音頻檢索也有兩種基本模式基于示例/基于查詢?cè)~音頻檢索的困難音頻信號(hào)種類繁多，環(huán)境噪聲差異性大聲學(xué)特征提取音頻信號(hào)常具有高度的時(shí)變性，只有在一個(gè)較短的時(shí)間段內(nèi)才可視為平穩(wěn)的分幀操作:語(yǔ)音信號(hào)，一般以20ms左右為一幀為去除邊界效應(yīng)，相鄰幀要相互重疊，常用的比例是1/2時(shí)域特征第n幀信號(hào)的短時(shí)能量第n幀信號(hào)的短時(shí)平均幅度第n幀信號(hào)的短時(shí)過(guò)零率頻域特征—LPC參數(shù)頻域上的語(yǔ)音譜S(z)是激勵(lì)譜E(z)通過(guò)傳遞函數(shù)為V(z)的線性系統(tǒng)后產(chǎn)生的輸出語(yǔ)音信號(hào)產(chǎn)生模型把實(shí)際聲道近似為P段不同截面積的短聲管的串聯(lián)，采用全極點(diǎn)模型將上式右側(cè)第二項(xiàng)看作s(n)的線性預(yù)測(cè)值s‘(n)，將Ge(n)看作誤差項(xiàng)，則聲道參數(shù)ai可以通過(guò)求解線性預(yù)測(cè)參數(shù)的最小均方誤差準(zhǔn)則求得轉(zhuǎn)換到時(shí)域，語(yǔ)音信號(hào)s(n)和激勵(lì)信號(hào)e(n)之間的關(guān)系為Mel倒譜系數(shù)MFCC人耳對(duì)臨界帶寬內(nèi)的音調(diào)具有掩蔽效應(yīng)當(dāng)兩個(gè)頻率相近的音調(diào)同時(shí)發(fā)出時(shí)只能聽(tīng)到一個(gè)音調(diào)MFCC的提取過(guò)程通過(guò)Mel頻率濾波器組得到信號(hào)的Mel頻率HMM模型Markov模型可用離散時(shí)域有限狀態(tài)機(jī)FSM描述FSM有N種狀態(tài)，用1～N表示，在時(shí)刻t所處的狀態(tài)用qt表示每個(gè)狀態(tài)下可能的輸出值的為O={o1,…,oM}FSM初始化時(shí)可位于N個(gè)狀態(tài)中的任何一個(gè)，其初始狀態(tài)分布為πi

=P(q1=i)，i=1,…,NFSM在當(dāng)前狀態(tài)以某種概率向任意的狀態(tài)跳轉(zhuǎn)，狀態(tài)轉(zhuǎn)移概率矩陣用A表示，A={aij}如果在任意時(shí)刻t，外界都看不到FSM的內(nèi)部狀態(tài)qt，只能得到一個(gè)觀測(cè)值ot，而ot與qt之間的關(guān)系可用條件概率P(ot|qt=j)來(lái)描述，則稱此Markov模型HMMHMM的描述HMM可用符號(hào)λ={A,B,π}來(lái)描述A為狀態(tài)轉(zhuǎn)移概率矩陣A={aij}N×NB為觀測(cè)值概率矩陣B={bj(ot)}N×Tπ為初始狀態(tài)分布π={πi}HMM的示意圖HMM的三個(gè)基本問(wèn)題識(shí)別問(wèn)題對(duì)于給定的觀測(cè)序列O=(o1,…,oT)和模型λ={A,B,π}，計(jì)算由λ產(chǎn)生O的概率P(O|λ)，常用前向和后向算法譯碼問(wèn)題對(duì)于給定的O

和λ，求λ對(duì)應(yīng)于O的最佳狀態(tài)序列Q*,即尋找使P(O|λ)達(dá)到最大時(shí)，O所對(duì)應(yīng)的狀態(tài)序列，一般采用Viterbi算法求解訓(xùn)練問(wèn)題對(duì)于給定的O，如何修正λ，使得λ產(chǎn)生O的概率最大，一般采用Baum-Welch算法求解HMM的基本問(wèn)題的經(jīng)典算法識(shí)別問(wèn)題前向、后向算法:從入口狀態(tài)或出口狀態(tài)開(kāi)始遞推的方法。兩種算法可以單獨(dú)使用，也可結(jié)合使用譯碼問(wèn)題Viterbi算法:基于動(dòng)態(tài)規(guī)劃的方法搜索HMM模型中對(duì)應(yīng)觀測(cè)序列O的可能性最大的狀態(tài)序列X*訓(xùn)練問(wèn)題Baum-Welch算法是一種廣義的EM算法，利用R個(gè)觀測(cè)序列迭代估計(jì)HMM的參數(shù)λ基于HMM的語(yǔ)音識(shí)別統(tǒng)一框架大詞匯量連續(xù)語(yǔ)音識(shí)別系統(tǒng)聲學(xué)模型聲學(xué)模型基于HM